Generalizing earlier work characterizing the quantum query complexity of computing a function of an unknown classical ``black box'' function drawn from some set of such black box functions, we investigate a more general quantum query model in which the goal is to compute functions of $N imes N$ ``black box'' unitary matrices drawn from a set of such matrices, a problem with applications to determining properties of quantum physical systems. We characterize the existence of an algorithm for such a query problem, with given query and error, as equivalent to the feasibility of a certain set of semidefinite programming constraints, or equivalently the infeasibility of a dual of these constraints, which we construct. Relaxing the primal constraints to correspond to mere pairwise near-orthogonality of the final states of a quantum computer, conditional on the various black-box inputs, rather than bounded-error distinguishability, we obtain a relaxed primal program the feasibility of whose dual still implies the nonexistence of a quantum algorithm. We use this to obtain a generalization, to our not-necessarily-commutative setting, of the ``spectral adversary method'' for quantum query lower bounds.
Generalizing earlier work characterizing the quantum query complexity of computing a function of an unknown classical black box'' function drawn from some set of such black box functions, we investigate a more general quantum query model in which the goal is to compute functions of $N imes N$ black box'' unitary matrices drawn from a set of such matrices, a problem with applications to determining properties of quantum physical systems. We characterize the existence of an algorithm for such a query problem, with given query and error, as equivalent to the feasibility of a certain set of semidefinite programming constraints, or equivalently the infeasibility of a dual of these constraints, which we construct. Relaxing the primal constraints to correspond to mere pairwise near-orthogonality of the final states of a quantum computer, conditional on the various black-box inputs, rather than bounded-error distinguishability, we obtain a relaxed primal program the feasibility of whose dual still implies the nonexistence of a quantum algorithm. We use this to obtain a generalization, to our not-necessarily-commutative setting, of the ``spectral adversary method'' for quantum query lower bounds.
We reformulate quantum query complexity in terms of inequalities and equations for a set of positive semidefinite matrices. Using the new formulation we: 1) show that the workspace of a quantum computer can be limited to at most n+k qubits (where n and k are the number of input and output bits respectively) without reducing the computational power of the model; 2) give an algorithm that on input the truth table of a partial Boolean function and an integer t runs in time polynomial in the size of the truth table and estimates, to any desired accuracy, the minimum probability of error that can be attained by a quantum query algorithm attempts to evaluate f in t queries; 3) use semidefinite programming duality to formulate a dual SDP P/spl circ/(f, t, /spl epsi/) that is feasible if and only if f cannot be evaluated within error /spl epsi/ by a t-step quantum query algorithm. Using this SDP, we derive a general lower bound for quantum query complexity that encompasses a lower bound method of Ambainis and its generalizations; 4) give an interpretation of a generalized form of branching in quantum computation.
Quantum query complexity measures the number of input bits that must be read by a quantum algorithm in order to evaluate a function. Hoyer et al. (2007) have generalized the adversary semidefinite program that lower-bounds quantum query complexity. By giving a matching quantum algorithm, we show that the general adversary lower bound is tight for every boolean function. The proof is based on span programs, a linear-algebraic computational model without inherent dynamics. Span programs correspond to solutions to the dual semi-definite program, and to bipartite graphs. The analysis shows that properties of eigenvalue-zero eigenvectors of the graphs in fact imply an “effective” spectral gap around zero We thus develop a quantum algorithm for evaluating span programs. It follows that span programs, measured by witness size, and quantum algorithms, measured by query complexity, are equivalent computational models, up to a constant factor. The result efficiently characterizes the quantum query complexity of a read-once formula over any finite gate set. It also implies that the quantum query complexity of the composition f ◦ (g, . . . , g) of two boolean functions matches the product of the query complexities of f and g, without a logarithmic factor for error reduction. The algorithm alternates a fixed reflection with input queries. Originally introduced for solving the unstructured search problem, this structure is therefore a universal feature of quantum query algorithms. We give a second algorithm for evaluating span programs that has the further potential to be time-efficient. Subsequent applications have derived nearly time-optimal quantum algorithms for evaluating many read-once formulas. Span programs may have promise for developing more quantum algorithms.
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 efficiently characterizes the quantum query complexity of a read-once formula over any finite gate set. It further shows that span programs are equivalent to quantum query algorithms.
In recent years, semidefinite programming has played a vital role in shaping complexity theory and quantum computing. There have been numerous applications ranging from estimating quantum values, over approximating combinatorial quantities, to proving various bounds. This work extends the use of semidefinite programs (SDPs) to proving product rules and to characterizing quantum query complexity. In the first application, we provide a general framework to establishing product rules for quantities that can be expressed (or approximated) using SDPs. We use duality theory to give product rules, which bound the value of the ``product'' of two problems in terms of their value. Some previous results have implicitly used the properties of SDPs to give such product rules. Here we give sufficient and necessary conditions under which these approaches work, thereby enabling us to capture these previous results under our unified framework. We also include a discussion about alternate definitions of what a ``product'' means and how they fit into our approach. The second application provides an SDP characterization of quantum query complexity, which is one of the ways in which complexity of a function can be measured. It is known that quantum query complexity can be lower bounded by the so-called ``adversary method'' which is expressible as a semidefinite program. Recently, Ben Reichardt showed that the adversary method leads to a tight lower bound for boolean functions by converting the solution of this SDP (of adversary method) into an algorithm. We show that a related SDP, called ``witness size'' in this thesis, provides a tight bound on the quantum query complexity of non boolean functions (total as well as partial). This witness size SDP is also used to give composition results for quantum query complexity. We also show that the witness size is bounded by a constant multiple of the adversary bound. Finally, we briefly explore whether other convex programming paradigms can be useful in complexity theory. One of them is copositive programming. We show that one of the recent result about parallel repetition of unique games, by Barak et.al., can be interpreted as an application of copositive programming.
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.
The general adversary bound is a semi-definite program (SDP) that lower-bounds the quantum query complexity of a function. We turn this lower bound into an upper bound, by giving a quantum walk algorithm based on the dual SDP that has query complexity at most the general adversary bound, up to a logarithmic factor. In more detail, the proof has two steps, each based on "span programs," a certain linear-algebraic model of computation. First, we give an SDP that outputs for any boolean function a span program computing it that has optimal "witness size." The optimal witness size is shown to coincide with the general adversary lower bound. Second, we give a quantum algorithm for evaluating span programs with only a logarithmic query overhead on the witness size. The first result is motivated by a quantum algorithm for evaluating composed span programs. The algorithm is known to be optimal for evaluating a large class of formulas. The allowed gates include all constant-size functions for which there is an optimal span program. So far, good span programs have been found in an ad hoc manner, and the SDP automates this procedure. Surprisingly, the SDP's value equals the general adversary bound. A corollary is an optimal quantum algorithm for evaluating "balanced" formulas over any finite boolean gate set. The second result extends span programs' applicability beyond the formula-evaluation problem. We extend the analysis of the quantum algorithm for evaluating span programs. The previous analysis shows that a corresponding bipartite graph has a large spectral gap, but only works when applied to the composition of constant-size span programs. We show generally that properties of eigenvalue-zero eigenvectors in fact imply an "effective" spectral gap around zero. A strong universality result for span programs follows. A good quantum query algorithm for a problem implies a good span program, and vice versa. Although nearly tight, this equivalence is nontrivial. Span programs are a promising model for developing more quantum algorithms.