Quantum query algorithms and lower bounds

김정산

Andris Ambainis

We propose a new method for proving lower bounds on quantum query algorithms. Instead of a classical adversary that runs the algorithm with one input and then modifies the input, we use a quantum adversary that runs the algorithm with a superposition of inputs. If the algorithm works correctly, its state becomes entangled with the superposition over inputs. We bound the number of queries needed to achieve a sufficient entanglement and this implies a lower bound on the number of queries for the computation. Using this method, we prove two new $Ω(\sqrt{N})$ lower bounds on computing AND of ORs and inverting a permutation and also provide more uniform proofs for several known lower bounds which have been previously proven via variety of different techniques.

Christoph Dürr, xb b b

Morris, Jackson, Fang Song

Given a graph $G$ with $n$ vertices and maximum degree $Δ$, it is known that $G$ admits a vertex coloring with $Δ+ 1$ colors such that no edge of $G$ is monochromatic. This can be seen constructively by a simple greedy algorithm, which runs in time $O(nΔ)$. Very recently, a sequence of results (e.g., [Assadi et. al. SODA'19, Bera et. al. ICALP'20, Alon Assadi Approx/Random'20]) show randomized algorithms for $(ε+ 1)Δ$-coloring in the query model making $\tilde{O}(n\sqrt{n})$ queries, improving over the greedy strategy on dense graphs. In addition, a lower bound of $Ω(n\sqrt n)$ for any $O(Δ)$-coloring is established on general graphs. In this work, we give a simple algorithm for $(1 + ε)Δ$-coloring. This algorithm makes $O(ε^{-1/2}n\sqrt{n})$ queries, which matches the best existing algorithms as well as the classical lower bound for sufficiently large $ε$. Additionally, it can be readily adapted to a quantum query algorithm making $\tilde{O}(ε^{-1}n^{4/3})$ queries, bypassing the classical lower bound. Complementary to these algorithmic results, we show a quantum lower bound of $Ω(n)$ for $O(Δ)$-coloring.

Uwe Schöning, Randall J. Pruim

Andris Ambainis, András Gilyén, Martins Kokainis

We study hybrid quantum-classical algorithms in the query model. The computation consists of quantum subroutines that make at most $q$ oracle queries; between subroutines, all qubits are measured and discarded. We prove matching upper and lower bounds for several problems in this model: (i) (Unbiased) Phase estimation up to a precision $ε$ requires $Θ(\frac{1}{q ε^2})$ queries; (ii) (Unbiased) Amplitude estimation up to a precision $ε$ requires $Θ(\frac{p(1-p)}{q ε^2})$ queries; (iii) Search among $N$ items requires $Θ(\frac{N}{q})$ queries; (iv) Two level AND-OR tree (AND of $m$ ORs, with $n$ inputs to each OR) requires $Θ(\frac{nm}{q})$ queries. All of these bounds are optimal up to a constant factor, for all $q$ from 1, corresponding to the classical complexity, to $Q(f)$, the unrestricted quantum query complexity of the respective problem. We also derive a hybrid lower bound for distinguishing two distributions specified by a state-preparation unitary; this bound is tight up to a logarithmic factor. Besides specific lower bounds, an important contribution is developing methods for proving lower bounds on hybrid quantum algorithms (which have been very ad-hoc up to now). The first two bounds follow from a common framework: we analyze probability distributions over measurement transcripts and bound a progress measure that captures their distinguishability. The AND-OR bound requires a more delicate argument, combining two progress measures that track the information available to the algorithm classically and in quantum form, respectively.