SIAM Journal on Computing · 2019 · 22 citations · 42 references
ComputingComputer ScienceMathematicsAlgorithmsQuantum ComputingTheory Of ComputationQuadratic FormsQuantum AlgorithmsQuantum Complexity TheoryQuantum ComputationQuantum Information TheoryChannelsQuantum Algorithm Complexity AnalysisQuantum Algorithmic ComplexityQuantum ChannelsQuantum ComplexityQuantum Query ComplexityQuery Complexity
We prove a characterization of $t$-query quantum algorithms in terms of the unit ball of a space of degree-$(2t)$ polynomials. Based on this, we obtain a refined notion of approximate polynomial degree that equals the quantum query complexity, answering a question of Aaronson et al. [``Polynomials, Quantum Query Complexity, and Grothendieck's Inequality,” in Proceedings of the 31st Conference on Computational Complexity, CCC 2016, Schloss Dagstuh, 2016, pp. 25:1--25:19]. Our proof is based on a fundamental result of Christensen and Sinclair [J. Funct. Anal., 72 (1987), pp. 151--181] that generalizes the well-known Stinespring representation for quantum channels to multilinear forms. Using our characterization, we show that many polynomials of degree four are far from those coming from two-query quantum algorithms. We also give a simple and short proof of one of the results of Aaronson et al. showing an equivalence between one-query quantum algorithms and bounded quadratic polynomials.
42
A fast quantum mechanical algorithm for database search
Lov K. Grover · 1996 · 8.6K citations · Full text
Convergence of Stochastic Processes.
Peter M. Robinson, David Pollard · Economica · 1985 · 2.3K citations
Strengths and Weaknesses of Quantum Computing
Charles H. Bennett, Ethan Bernstein, Gilles Brassard et al. · SIAM Journal on Computing · 1997 · 1.5K citations · Full text
On the Power of Quantum Computation
Daniel Simón · SIAM Journal on Computing · 1997 · 1.3K citations
Computing, Computer Science, Physics +14