Source-linked AI summary
Reflections for quantum query algorithms
Ben W. Reichardt
TL;DR
The paper addresses whether the general adversary lower bound and span-program-based quantum algorithms can be made exactly tight without the prior logarithmic overhead. It constructs a direct dual-SDP algorithm alternating two reflections, proving optimal bounded-error query complexity and exact composition, while leaving broader classical–quantum query relationships open.
Problem
The prior span-program algorithm was tight only up to a sub-logarithmic factor caused by converting a continuous-time query algorithm into a discrete-query algorithm.
Method
The paper uses the dual SDP for the general adversary bound to construct a simpler algorithm alternating the input oracle with a fixed reflection.
Results
The general adversary bound exactly characterizes quantum query complexity for boolean functions, and composed boolean functions achieve the product of their query complexities without logarithmic error reduction.
Takeaways & Limitations
Every boolean function has an optimal bounded-error two-reflections algorithm, and span programs are equivalent to quantum query algorithms for boolean-function evaluation.
Takeaways & Limitations
The relationship between classical and quantum query complexities for total functions remains open; the best stated upper bound is D(f)=O(Q(f)^6).
Abstract
from arXiv · showhide
We show that any boolean function can be evaluated optimally by a quantum query algorithm that alternates a certain fixed, input-independent reflection with a second reflection that coherently queries the input string. Originally introduced for solving the unstructured search problem, this two-reflections structure is therefore a universal feature of quantum algorithms. Our proof goes via the general adversary bound, a semi-definite program (SDP) that lower-bounds the quantum query complexity of a function. By a quantum algorithm for evaluating span programs, this lower bound is known to be tight up to a sub-logarithmic factor. The extra factor comes from converting a continuous-time query algorithm into a discrete-query algorithm. We give a direct and simplified quantum algorithm based on the dual SDP, with a bounded-error query complexity that matches the general adversary bound. Therefore, the general adversary lower bound is tight; it is in fact an SDP for quantum query complexity. This implies that the quantum query complexity of the composition f(g,...,g) of two boolean functions f and g matches the product of the query complexities of f and g, without a logarithmic factor for error reduction. It further shows that span programs are equivalent to quantum query algorithms.
1 Introduction
The paper proves that the general adversary bound exactly characterizes bounded-error quantum query complexity and gives a simpler algorithm alternating two reflections. This yields optimal composition results and establishes an equivalence between span programs and quantum query algorithms.
- Motivation: The previous span-program approach incurred an unnatural log-over-log-log factor from converting a continuous-time algorithm into a discrete-query algorithm.
- Main result: The general adversary bound characterizes quantum query complexity for every function f:D→{0,1}.
- Composition: For boolean functions f and g, the quantum query complexity of their composition matches the product of their individual query complexities without a logarithmic error-reduction factor.
- Algorithm: The new algorithm alternates the input oracle with a fixed reflection derived from the dual SDP for the general adversary bound.
- Algorithm: Every boolean function can therefore be evaluated with bounded error using two alternating reflections, generalizing the structure of Grover’s search algorithm.
- Consequences: Because optimal span-program witness size equals the general adversary bound, span programs and quantum query algorithms are equivalent computational models for evaluating boolean functions.
2 The algorithms
The algorithms are built from a feasible dual-SDP solution and evaluate the function using alternating reflections, with three increasingly simplified variants. Each achieves O(W) query complexity, while the efficient implementation of the fixed reflection remains unclear.
- Algorithmic framework: A feasible dual-SDP solution with objective value W yields three bounded-error algorithms for evaluating f, each using O(W) queries.The SDP value also equals the witness size of a corresponding canonical span program.
- Algorithmic framework: The graph construction uses a weighted bipartite graph derived from the SDP solution, with vertices representing F_0, the output vertex 0, and index set I.Edges are weighted by entries of the graph’s biadjacency matrix.
- Reflection-based algorithm: The unitary U_x alternates a fixed reflection independent of x with a reflection determined by the input, and the latter uses one input-oracle call.The fixed reflection projects onto the eigenvalue-zero subspace of the graph adjacency matrix; the input-dependent reflection excludes vertices associated with complemented input bits.
- Three algorithm variants: The second and third algorithms choose a random evolution time and apply U_x, with the third outputting 1 exactly when the measured vertex is |0⟩.The stated procedures use T uniformly from ranges scaling as 100W and 10^5W, respectively.
3 Analysis of the algorithms
The analysis studies the spectrum of a product of reflections and transfers graph-based spectral properties to the unitary used by the algorithms. These bounds establish completeness and soundness for the algorithms, including explicit success-probability gaps.
- Spectral analysis: The analysis studies U_x = (2Π_x − 1)(2∆ − 1) through the spectrum of a product of reflections.The proof uses the eigen-decomposition of products of two projections to analyze the unitary’s invariant subspaces.
- Spectral analysis: For f(x) = 1, U_x has an eigenvalue-one eigenvector, while for f(x) = 0, its small-phase eigenspaces have bounded overlap with |0⟩.The latter statement is obtained by translating the graph effective spectral-gap lemma into an analogous unitary statement.
- Correctness: The first algorithm outputs 1 with probability at least 4/5 when f(x) = 1 and at most 2/5 when f(x) = 0.These bounds follow from Lemma 3.4 with the stated phase-estimation parameters.
- Graph-to-unitary translation: The graph construction links the input-dependent graph G(x) to the fixed graph G and enables the spectral-gap argument underlying Lemma 3.4.The proof uses AG∆ = 0 and the relation AG(x)∆ = T(1 − Π_x), then restricts the accepting eigenvector to G.
- Correctness: The third algorithm outputs 1 with probability at least 64% for f(x) = 1 and at most 61% for f(x) = 0.The analysis sets τ = ⌈10^5W⌉ and chooses Λ = π − Θ with Θ = 1/(2000W).