Quantum query complexity

Artem Kaznatcheev lecturing on quantum query complexityYou probably noticed a few things about TheEGG: a recent decrease in blog post frequency and an overall focus on the algorithmic lens — especially its view of biology. You might also be surprised by the lack of discussion of quantum information processing: the most successful on-going application of the algorithmic lens. I actually first became passionate about cstheory as a lens on science when I was studying quantum computing. In undergrad, I played around with representation theory and other fun math to prove things about a tool in quantum information theory known as unitary t-designs. At the start of grad school, I became more algorithmic by focusing on quantum query complexity. To kill two birds with one stone, I thought I would introduce you to query complexity and in doing so restore the more regular posting schedule you’ve been accustomed to. Of course, the easiest way to do this is to recycle my old writing from the now stale cstheory StackExchange blog.

How hard is it to answer a question? As theoretical computer scientists, this query haunts us. We formalize a ‘question’ as a function on some input and ‘answering’ as running a finite procedure. This procedure might run on a Turing Machine, your cellphone, or a quantum computer. ‘Hard’ is quantified by use of resources such as energy, space or time. Unfortunately, the most popular notion of hardness — time complexity — is notoriously difficult to characterize in a quantum computing model. If we want to show what a model of computation can and can’t do, we must use a related, but simpler measure of complexity. For quantum computing this measure is quantum query complexity. This post explains quantum query complexity and lays the foundations for future entries that will introduce the lower bound technique of the (negative) adversary method, and show how it characterizes quantum query complexity through its connection to span programs.

In the query model, the input to our algorithm is given as a black-box (called the oracle). We can only gain knowledge about the input by asking the oracle for individual bits. The input is a bit-string x \in D \subseteq \{0, 1\}^n and the goal is to compute some function f : D \rightarrow \{0,1\}. If D = \{0,1\}^n then we call the function total. For simplicity, we only consider decision problems (binary range), although the machinery has been developed for functions over finite strings in arbitrary finite input and output alphabets.

The query complexity of a function is the minimum number of queries used by any circuit computing the function. For a two-sided error \epsilon, we denote the query complexity by Q_\epsilon(f). Since success amplification is straightforward, we abbreviate further by setting Q(f) = Q_{1/3}(f). Similar measures exist for classical algorithms, where this model is more frequently referred to as decision-tree complexity. The usual notation is D(f) for deterministic query complexity, R(f) for two-sided error (1/3) randomized query complexity, and C(f) for certificate (or non-deterministic) complexity. We specify our model concretely, following [HS05]:

Quantum query model: formally

The memory of a quantum query algorithm is described by three Hilbert spaces (registers): the input register, H_I, which holds the input x \in D, the query register, H_Q, which holds an integer 1 \leq i \leq n and a bit b \in \{0,1\}, and the working memory, H_W, which holds an arbitrary value. The query register and working memory together form the memory accessible to the algorithm, denoted H_A. The unitaries that define the algorithm can only act on this space. The accessible memory of a quantum query algorithm is initialized to a fixed state. On input x the initial state of the algorithm is |x\rangle_I \otimes |1, 0\rangle_Q \otimes |0\rangle_W. The state of the algorithm then evolves through queries, which depend on the input register, and accessible memory operators which do not.

A query is a unitary operator where the oracle answer is given in the phase. We definite the operator O by its action on the basis state |x\rangle_I \otimes |i,b\rangle_Q as

O |x\rangle_I \otimes |i,b\rangle_Q = (-1)^{bx_i} |x\rangle_I \otimes |i,b\rangle_Q

The accessible memory operator is an arbitrary unitary operation U on the accessible memory H_A. This operation is extended to act on the whole space by interpreting it as I_I \otimes U and O is interpreted as O \otimes I_W. Thus the state of the algorithm on input x after t queries can be written as:

|x\rangle_I |\psi^t_x\rangle_A = U_t O U_{t-1} ... U_1 O U_0 |x\rangle_I |1, 0\rangle_Q |0\rangle_W

Where we noticed that the input register is left unchanged by the algorithm. The output of a T-query algorithm is distributed according to the state of the accessible memory |\psi^T_x\rangle and two projections \Pi_0 and \Pi_1 such that \Pi_0 + \Pi_1 = I corresponding to the possible outcomes of a decision problem. The probability that given input x the algorithm returns 0 is ||\Pi_0|\psi^T_x\rangle||^2 and 1 is ||\Pi_1|\psi^T_x\rangle||^2. Q_\epsilon(f) is the minimum number of queries made by an algorithm which outputs f(x) with probability 1 - \epsilon for every x.

Relations between models

For partial functions, the quantum query complexity can be exponentially smaller than randomized or deterministic query complexity [Sho95, BV97, Sim97, Aar10]. However, if the partial function is invariant under permuting inputs and outputs then the complexities are polynomially related with R(f) = O(Q(f)^9) [AA09]. If the function is total, then D(f) is bounded by O(Q(f)^6) , O(Q(f)^4) for monotone total functions, and O(Q(f)^2) for symmetric total functions [BBC+01]. However, no greater than quadratic separations are known for total functions (this separation is achieved by OR, for example). This has led to the conjecture that for total functions D(f) = O(Q(f)^2). This conjecture is open for all classes of total functions, except monotone [BBC+01], read-once [BS04], and constant-sized 1-certificate functions.

The infamous time complexity is always at least as large as the query complexity since each query takes one unit step. For famous algorithms such as Grover’s search [Gro96] and Shor’s period finding (which is the quantum part of his famed polynomial time factoring algorithm) [Sho95], the time complexity is within poly-logarithmic factors of the query complexity. There are also exceptions to the tight correspondence. The Hidden Subgroup Problem has polynomial query complexity [EHK04], yet polynomial time algorithms are not known for the problem.

By taking the computation between queries as free, we get a handle for producing lower bounds. This allows us to develop strong information-theoretic techniques for lower bounding quantum query complexity. In my next post I will use this framework to develop the (negative) adversary method.

I originally wrote this post for the CSTheory Community Blog where it was published on July 21, 2011. Unfortunately, that blog is largely defunct, so I decided to repost here with slight modifications. Photo is by Momo Lu Yin from the National University of Singapore, and captures me introducing physicists to query complexity during the first AQuA Graduate Student Congress held at Singapore’s Centre for Quantum Technologies in December 2010.


[AA09] Scott Aaronson and Andris Ambainis. The need for structure in quantum speedups. 2009, arXiv:0911.0996v1 [quant-ph].

[Aar10] Scott Aaronson. BQP and the polynomial hierarchy. In Proceedings of the 42nd ACM symposium on Theory of computing, pages 141-150. ACM, 2010, arXiv:0910.4698 [quant-ph].

[BBC+01] R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf. Quantum lower bounds by polynomials. Journal of the ACM (JACM), 48(4):778-797, 2001.

[BS04] H. Barnum, and M. Saks. A lower bound on the quantum query complexity of read-once functions. Journal of Computer and System Sciences, 69(2):244-258, 2004. arXiv:quant-ph/0201007v1

[BV97] E. Bernstein and U. Vazirani. Quantum complexity theory. SIAM J. Comput., 26(5):1411-1473, 1997.

[EHK04] M. Ettinger, P. Hoyer, and E. Knill. The quantum query complexity of the hidden subgroup problem is polynomial. Information Processing Letters, 91(1):43-48, 2004, arXiv:quant-ph/0401083v1.

[Gro96] L.K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 212-219. ACM, 1996, arXiv:quant-ph/9605043.

[HS05] P. Hoyer, and R. Spalek. Lower Bounds on Quantum Query Complexity. Bulletin of the European Association for Theoretical Computer Science, 87, 2005. arXiv:quant-ph/0509153v1.

[Sim97] Simon, D.R. (1997). On the power of quantum computation. SIAM Journal on Computing, 26 DOI: 10.1137/S0097539796298637

[Sho95] P.W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput., 26:1484-1509, 1995, arXiv:quant-ph/9508027.


About Artem Kaznatcheev
From the Department of Computer Science at Oxford University and Department of Translational Hematology & Oncology Research at Cleveland Clinic, I marvel at the world through algorithmic lenses. My mind is drawn to evolutionary dynamics, theoretical computer science, mathematical oncology, computational learning theory, and philosophy of science. Previously I was at the Department of Integrated Mathematical Oncology at Moffitt Cancer Center, and the School of Computer Science and Department of Psychology at McGill University. In a past life, I worried about quantum queries at the Institute for Quantum Computing and Department of Combinatorics & Optimization at University of Waterloo and as a visitor to the Centre for Quantum Technologies at National University of Singapore. Meander with me on Google+ and Twitter.

3 Responses to Quantum query complexity

  1. Pingback: Lower bounds by negative adversary method | Theory, Evolution, and Games Group

  2. Pingback: Sherlock Holmes and the Case of the Missing Replication | Theory, Evolution, and Games Group

  3. Pingback: Cataloging a year of blogging: the algorithmic world | Theory, Evolution, and Games Group

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s