Abstract
I offer a case that quantum query complexity still has loads of enticing and fundamental open problems—from relativized
1 INTRODUCTION
Quantum query complexity (see [24] for a classic survey) is the study of how many queries a quantum computer needs to make to an input string X to learn various properties of X. The key here is that a single query can access multiple bits of X, one in each branch of a superposition state. For over 30 years, this subject has been a central source of what we know about both the capabilities and the limitations of quantum computers.
In my view, there are two reasons query complexity has played such an important role in quantum computing theory as a whole. First, it so happens that most of the famous quantum algorithms—including Deutsch-Jozsa [26], Bernstein-Vazirani [21], Simon [48], Shor [47], and Grover [33]—fit naturally into the query complexity framework, or (in the case of Shor’s algorithm) have a central component that does. Second, query complexity lets us prove not only upper bounds but also nontrivial and informative lower bounds—as illustrated by the seminal 1994 theorem of Bennett et al. [20] that a quantum computer needs queries to search an unordered list of size N for a single “marked item.” This both demonstrated the optimality of Grover’s algorithm, 2 years before that algorithm had been discovered to exist (!), and showed the existence of an oracle relative to which .
Of course, oracle separations sometimes mislead us about the “real world,” where no oracles are present—a famous example being the 1990 theorem [45]. Even after a quarter century, though, nonrelativizing techniques (i.e., techniques that transcend query complexity) have made only minor inroads into quantum complexity theory, at least outside the usual place where those techniques have shined: namely, the study of interactive proof systems.
Yet today, some in our field seem to have the impression that quantum query complexity is more or less a closed subject. Certainly, some of quantum computing theorists’ attention has understandably shifted to other topics, from the theoretical foundations of quantum supremacy experiments [39], to potential near-term or “NISQ” quantum algorithms [42], to the quest to prove a quantum PCP Theorem [10]. And certainly, many of the great open problems of quantum query complexity from circa 2000 were ultimately solved: to give some well-known examples, the quantum query complexities of the collision and element distinctness problems [9] and of evaluating read-once formulas [44]; the optimal separation between deterministic and quantum query complexities of total Boolean functions [7, 16]; and an oracle separation between and the polynomial hierarchy [43].
Nevertheless, in this article I’d like to make the case that open problems abound in quantum query complexity—and I don’t mean detail problems, of tightening some bound to remove a logarithmic factor, but big, juicy, important problems. Some of my problems are old and well known; others are obscure; still others, as far as I know, appear here in writing for the first time.
2 and Oracle Separations
Recall that , Quantum Merlin Arthur, is the class of languages L for which membership in L can be proven via a polynomial-size quantum witness state that’s verified in quantum polynomial time. In 2002, Aharonov and Naveh [12] defined , or Quantum Classical Merlin Arthur, to be the subclass of where the witness is required to be a classical basis state (i.e., a string). Ever since, one of the fundamental problems of quantum complexity theory has been whether . One distinctive feature of this question is that even its query complexity analog remains open:
Is there an oracle relative to which ?
In 2007, Greg Kuperberg and I [8] at least showed that there’s a quantum oracle U—that is, a collection of unitary transformations provided as black boxes—such that . This was the first use of quantum oracles in complexity theory; their use has since become standard. But the question of whether and can be separated by a “standard” oracle remained wide open. In 2015, Fefferman and Kimmel [30] showed that there’s a “randomized, in-place” classical oracle relative to which , but for proving a conventional classical oracle separation, I believe the best candidate we have remains the “component mixers problem” introduced in 2011 by Lutomirski [40].
Here is another fundamental problem that’s remained open about and oracle separations:
Is there an oracle—even a quantum oracle—relative to which ?
Here, is the analog of to allow two unentangled Merlins, so that Arthur can always assume that the witness state he receives is a tensor product across two polynomial-size registers. Despite 18 years of work on this class, the only inclusions known are still the obvious ones, . Furthermore, unlike with the vs. problem, here we do not even have a quantum oracle relative to which . Watrous (see [5]) conjectured that there is no quantum channel that takes polynomially many qubits as input, produces polynomially many qubits as output, always produces an approximately separable state on two registers as its output, and can approximately produce any separable state. Proving Watrous’s “no disentanglers conjecture” is a prerequisite to separating from query complexity, since were his conjecture false, we could always use a witness to simulate a witness. See Harrow et al. [35] for the best current progress toward proving Watrous’s conjecture.
3 QUERY/SPACE TRADEOFFS
In the collision problem, we’re given black-box access to a function (where n is even and ) and are asked to decide whether f is 1-to-1 or 2-to-1, promised that one of those is the case. In the element distinctness problem, we’re given black-box access to a function , with no promise, and are simply asked whether f is 1-to-1.
What are the optimal tradeoffs between the number of queries used by a quantum algorithm to solve the collision or the element distinctness problems and the number of qubits or classical bits of memory?
Brassard et al. [22] gave a quantum algorithm for the collision problem that uses quantum queries, as well as bits of classical memory and qubits. Six years later, Ambainis [15] gave a quantum algorithm for element distinctness that uses quantum queries and qubits. The 2002 collision lower bound by me and Yaoyun Shi [9] showed that both of these algorithms were optimal in terms of queries, thereby settling the problems’ quantum query complexity.
Here, though, we’re asking whether a quantum algorithm for these problems could achieve near-optimal query complexity while also using a small memory. Note that, by using Grover’s algorithm, we could solve the collision problem using only qubits in total, but then we’d need queries rather than . For element distinctness, even supposing that we need a large memory, it would also be interesting to know whether the memory needs to be made of qubits or whether coherently queryable classical bits (a so-called “qRAM”) would suffice.
At present, unfortunately, the only techniques that we have for proving quantum lower bounds that trade off space with query complexity seem to apply only to problems with many bits of output, such as sorting a list [37]. Proving such lower bounds for decision problems, like collision or element distinctness, will probably require the invention of new techniques.
4 MAXIMAL SEPARATIONS
Given a total Boolean function , we denote by , , and the deterministic, (bounded-error) randomized, and (bounded-error) quantum query complexities of f, respectively. In their seminal 1998 paper, Beals et al. [18] showed that for all f. This stood as the best-known relationship between and until extremely recently, when, building on Huang’s breakthrough proof of the Sensitivity Conjecture [36], some of us [7] showed that for all total Boolean functions f.
In the other direction, until 2015 it was widely believed that the largest possible gap between classical and quantum query complexities for total Boolean functions was quadratic, and was achieved by Grover’s algorithm applied to the n-bit OR function. But Ambainis et al. [16] then refuted that conjecture by giving an example of a Boolean function f for which . Not long afterward, Ben-David [19] (see also Aaronson et al. [6]) gave an example of an f for which , thereby showing that Ambainis et al.’s separation was not just an artifact of ignoring classical randomized algorithms. Ben-David’s result was recently improved to give functions f for which [49] and even [17, 46].
Yet all this progress, as dramatic as it’s been, still leaves a gap between 3 and 4 in the exponent of the optimal separation between and .
What is the largest possible gap between and , for a total Boolean function f?
5 DEGREE OF PARTIAL FUNCTIONS
Let be a partial Boolean function, where . Define the approximate degree of f, or , to be the minimum degree of a real polynomial such that
(i) | for all , and | ||||
(ii) | for all . |
The seminal 1998 work of Beals at al. [18] showed that for all f, where is bounded-error quantum query complexity. This is simply because the acceptance probability of a T-query quantum algorithm is a real polynomial of degree at most . Beals et al.’s result was the beginning of the wildly successful polynomial method in quantum complexity theory, whose central idea is that to lower-bound quantum query complexity, it suffices to lower-bound approximate degree.
In 2003, Ambainis [14] showed that there can be small polynomial gaps between and for total Boolean functions f—and thus, “the polynomial method is not tight.” Ben-David, Kothari, and I [6] later improved this to get a fourth-power gap between and , which is tight by the recent work of Ben-David, Kothari, Rao, Tal, and me [7].
I ask about the situation for partial Boolean functions:
What is the largest possible gap between and for partial f? Can the gap even be exponential?
Note that, if it weren’t for requirement (ii)—namely, that the polynomial must be bounded in even on inputs that violate the promise—we’d have a degree-1 polynomial representing the n-bit OR function, whose quantum query complexity is .
6 UNITARY SYNTHESIS PROBLEM
In 2007, Greg Kuperberg and I [8] raised the following question:
For every n-qubit unitary transformation U, does there exist an oracle such that a machine can implement U?1
In my 2016 Barbados lecture notes [4], I took to calling this the “Unitary Synthesis Problem.” It remains wide open.
For comparison, it’s not hard to show that, for every n-qubit state , there exists an oracle A such that a machine can prepare . Indeed, for every n-qubit unitary U and every polynomial p, there exists an oracle A such that a machine can simulate the behavior of U on any chosen basis states. However, extending this construction to simulate U on all states seems to entail exponentially many queries to A.
While it might sound esoteric, the Unitary Synthesis Problem has turned up again and again—for example, in the study of the nonabelian hidden subgroup problem [29], of decoding Hawking radiation from a black hole [4, 34], and of schemes for quantum copy-protection and quantum money [2, 4]. In each of those topics, one is interested in certain complicated n-qubit unitary transformations U—and especially, whether or not those Us have polynomial-size quantum circuits. The question arises: could we at least show that small quantum circuits would exist if (say) or some other classical complexity classes dramatically collapsed? While the implication isn’t immediate, a positive answer to the Unitary Synthesis Problem would strongly suggest that the answer was yes. For what it’s worth, though, my conjecture is that the answer is negative—in which case, the study of quantum circuit complexity cannot be so easily related to classical complexity theory.
7 VERIFIABILITY OF QUANTUM COMPUTING
Let be the class of languages that admit classical interactive proofs. In the unrelativized world, [45], but it’s well known that the situation relative to oracles can be dramatically different [32]. Thus, we ask:
Does there exist an oracle A such that ?
In my view, the Forrelation problem, which I [3] introduced in 2009, and which Raz and Tal [43] used in 2018 to give an oracle relative to which , provides a compelling candidate for an oracle relative to which as well. However, showing that Forrelation is not in will require a new circuit lower bound—one that talks about circuits with “expectation” and “maximization” gates, rather than circuits with AND, OR, and NOT gates. As far as I know, Aiello et al. [13] proved what’s still the best-known lower bound against expectation/maximization circuits in 1989, when they gave an oracle relative to which more rounds give interactive protocols more power.
Now let be the subclass of consisting of all languages for which a prover can convince a verifier of a “yes” answer, through polynomially many rounds of classical interaction.
Is there at least an oracle relative to which ?
Besides Forrelation, even the complement of Simon’s Problem (i.e., output “yes” if f is a 1-to-1 function, or “no” if f satisfies the Simon promise, promised that one of these is the case) seems like a good candidate for an oracle problem in but not in . In the Simon example, note that there is an interactive protocol, based on approximate counting—it just doesn’t seem to be a protocol for which a machine could implement the prover’s strategy.
Finally, a question that was implicit in our previous one:
Are the celebrated protocols for blind and verified quantum computation, due to Broadbent et al. [23], Aharonov et al. [11], and Mahadev [41], inherently nonrelativizing?
Certainly these protocols don’t manifestly work relative to arbitrary oracles, but are there variants of the protocols that do?
8 GLUED TREES
In 2002, Childs et al. [25] gave a celebrated quantum walk algorithm that, informally, gets from the leftmost to the rightmost vertex in the following -sized graph in only time and with success probability:
By contrast, they showed that a randomized algorithm needs queries to an oracle encoding the graph to solve the same problem (improved by Fenner and Zhang [31] to ).
Suppose, however, that we actually want to find a path from left to right. Does even a quantum computer need queries for that task?
Certainly, if we try to measure the state of the quantum walk algorithm to reveal such a path, we’ll destroy the quantum interference that causes that algorithm to succeed. But this, of course, doesn’t show that no other quantum algorithm is possible. It seems to me that a lower bound—showing that a quantum algorithm can’t efficiently find even a single left-right path, even though it can traverse exponentially many such paths in superposition—would be a striking algorithmic version of wave/particle duality.
9 COMPARING QUERY MODELS
Given a function f, the usual model of quantum query complexity is that we get access to an oracle that maps basis states of the form to basis states of the form , where denotes bitwise XOR and where I’m ignoring workspace registers. However, if f is injective, then another model is possible: namely, an oracle that simply maps basis states of the form to basis states of the form , “erasing” the previous contents of the register. This second model has the great advantage of not leaving x around as garbage, but the disadvantage of not being inherently reversible.
In 2000, Elham Kashefi (personal communication) asked me the following question: are there sets of injective functions f for which a quantum computer can learn certain properties of f using few queries to an erasing oracle, but not using few queries to a standard oracle? I realized that a lower bound for the collision problem would naturally lead to an affirmative answer to this question. This provided a central motivation for my work on the collision problem [1], which, in an appendix, did give an affirmative answer to Kashefi’s question.
More recently, I became aware that the converse question is equally interesting:
Are there sets of injective functions f for which a quantum computer can learn certain properties of f using few queries to a standard oracle, but not using few queries to an erasing oracle?
One natural candidate would be as follows:
where h is a Simon function (i.e., a function that’s either 1-to-1 or else satisfies the Simon promise, and for which the promise is to decide which), and is a long string of random garbage depending on x. The inclusion of makes f injective with overwhelming probability but with a standard oracle is no bar to running Simon’s algorithm, since we can simply use a second oracle invocation to uncompute garbage:On the other hand, the garbage seems to make erasing queries no more useful than classical queries. A central reason I’m interested in this conjecture is that a proof of it seems likely to proceed by proving a much more general statement, about the presence of a sufficient amount of garbage, in an erasing oracle’s responses, being equivalent (under appropriate conditions) to decohering or measuring the responses.
10 THE LINEAR CROSS-ENTROPY BENCHMARK
In fall 2019, a team at Google reported the achievement of quantum supremacy based on a sampling benchmark with superconducting qubits [27]. In summer 2021, a team at USTC in China reported an independent replication [28]. Briefly, in these experiments, one generates a random quantum circuit C acting on n qubits (in the Google experiment, ; in the USTC experiment, ). One then uses a quantum computer to (hopefully) sample from , the probability distribution over n-bit strings induced by preparing the state and then measure all n qubits in the computational basis. Finally, having generated samples , one uses a classical computer to calculate
One can show that ideal sampling, with a noiseless quantum computer, would yield an expected value of , whereas classical random guessing would yield an expected value of . The test is considered a success if and only if is sufficiently bounded above 1. Google’s experiment achieved a value of .
One can ask: what if we wanted to achieve ? Would that problem be intractable even for a quantum computer—analogous to violating the Tsirelson inequality (i.e., the statement that even quantumly entangled players can win the CHSH game with probability at most )? If we imagined a black box able to output samples with, say, , would that black box provide “beyond quantum” computational abilities, and if so can we say anything about those abilities?
Here I ask a query complexity version of this question. Given a Boolean function , an easy quantum algorithm samples a string s with probability equal to , where is the Boolean Fourier coefficient of f. Define the quantity
Then one can show that repeating the Fourier sampling algorithm yields samples that satisfy . We now ask:What is the quantum query complexity of outputting samples that satisfy, say, ?
Very recently, Kretschmer [38] made significant progress on this problem by showing that
(1) | given an n-qubit Haar-random quantum oracle, queries are needed to violate the “quantum supremacy Tsirelson’s inequality” for that oracle (compared to an upper bound of ), and | ||||
(2) | when , the obvious quantum algorithm for Fourier-sampling a Boolean function f is optimal among all 1-query quantum algorithms. |
Acknowledgments
I thank Andrew Childs for the glued trees figure, and Travis Humble and Mingsheng Ying for commissioning this piece.
Footnotes
1 Technically, Kuperberg and I only asked whether this is true for a Haar-random U, but I expect the Haar-random case to be essentially the hardest case.
Footnote
- [1] . 2002. Quantum lower bound for the collision problem. In Proc. ACM STOC. 635–642.
quant-ph/0111102. Google ScholarDigital Library - [2] . 2009. Quantum copy-protection and quantum money. In Proceedings of IEEE Conference on Computational Complexity (CCC’09). 229–242. Google ScholarDigital Library
- [3] . 2010. BQP and the polynomial hierarchy. In Proc. ACM STOC.
arXiv:0910.4698. Google ScholarDigital Library - [4] . 2016. The complexity of quantum states and transformations: From quantum money to black holes. Lecture Notes for the 28th McGill Invitational Workshop on Computational Complexity, with guest lectures by A. Bouland and L. Schaeffer. www.scottaaronson.com/barbados-2016.pdf.Google Scholar
- [5] . 2008. The power of unentanglement. In Proc. Conference on Computational Complexity. 223–236.
arXiv:0804.0802. Google ScholarDigital Library - [6] . 2016. Separations in query complexity using cheat sheets. In Proc. ACM STOC. 863–876.
arXiv:1511.01937. Google ScholarDigital Library - [7] . 2021. Degree vs. approximate degree and quantum implications of Huang’s sensitivity theorem. In Proc. ACM STOC. 1330–1342.
arXiv:2010.12629. Google ScholarDigital Library - [8] . 2007. Quantum versus classical proofs and advice. Theory Comput. 3, 7 (2007), 129–157.
Earlier version in CCC’07. arXiv:quant-ph/0604056. Google ScholarCross Ref - [9] . 2004. Quantum lower bounds for the collision and the element distinctness problems. J. ACM 51, 4 (2004), 595–605. Google ScholarDigital Library
- [10] . 2013. The quantum PCP conjecture. SIGACT News 44, 2 (2013), 47–79.
arXiv:1309.7495. Google ScholarDigital Library - [11] . 2017. Interactive proofs for quantum computations.
Earlier version in ICS’10. arXiv:1704.04487. Google Scholar - [12] . 2002. Quantum NP - a survey.
quant-ph/0210077. Google Scholar - [13] . 1990. On the power of interaction. Combinatorica 10, 1 (1990), 3–25.
Earlier version in FOCS’86. Google ScholarCross Ref - [14] . 2006. Polynomial degree vs. Quantum query complexity. J. Comput. Sys. Sci. 72, 2 (2006), 220–238.
Earlier version in FOCS’03. quant-ph/0305028. Google ScholarDigital Library - [15] . 2007. Quantum walk algorithm for element distinctness. SIAM J. Comput. 37, 1 (2007), 210–239.
Earlier version in FOCS’04. quant-ph/0311001. Google ScholarDigital Library - [16] . 2017. Separations in query complexity based on pointer functions. J. ACM 64, 5 (2017), 1–24.
Earlier version in STOC’16. arXiv:1506.04719. Google ScholarDigital Library - [17] . 2021. K-forrelation optimally separates quantum and classical query complexity. In Proc. ACM STOC. 1303–1316.
arXiv:2008.07003. Google ScholarDigital Library - [18] . 2001. Quantum lower bounds by polynomials. J. ACM 48, 4 (2001), 778–797.
Earlier version in FOCS’98, pp. 352–361. quant-ph/9802049. Google ScholarDigital Library - [19] . 2015. A super-grover separation between randomized and quantum query complexities.
arXiv:1506.08106. Google Scholar - [20] . 1997. Strengths and weaknesses of quantum computing. SIAM J. Comput. 26, 5 (1997), 1510–1523.
quant-ph/9701001. Google ScholarDigital Library - [21] . 1997. Quantum complexity theory. SIAM J. Comput. 26, 5 (1997), 1411–1473.
Earlier version in STOC’93. Google ScholarDigital Library - [22] . 1997. Quantum algorithm for the collision problem. ACM SIGACT News 28 (1997), 14–19.
quant-ph/9705002. Google ScholarDigital Library - [23] . 2009. Universal blind quantum computation. In Proc. IEEE FOCS.
arXiv:0807.4154. Google ScholarDigital Library - [24] . 2002. Complexity measures and decision tree complexity: A survey. Theoretical Comput. Sci. 288 (2002), 21–43. Google ScholarDigital Library
- [25] . 2003. Exponential algorithmic speedup by a quantum walk. In Proc. ACM STOC. 59–68.
quant-ph/0209131. Google ScholarDigital Library - [26] . 1992. Rapid solution of problems by quantum computation. Proc. Roy. Soc. London A439 (1992), 553–558.Google ScholarCross Ref
- [27] 2019. Quantum supremacy using a programmable superconducting processor. Nature 574 (2019), 505–510.
arXiv:1910.11333. Google Scholar - [28] 2021. Strong quantum computational advantage using a superconducting quantum processor.
arXiv:2106.14734. Google Scholar - [29] . 2004. The quantum query complexity of the hidden subgroup problem is polynomial. Inform. Proc. Lett. 91, 1 (2004), 43–48.
quant-ph/0401083. Google ScholarDigital Library - [30] . 2018. Quantum vs. classical proofs and subset verification. In Mathematical Foundations of Computer Science. 1–22.
arXiv:1510.06750. Google Scholar - [31] . 2003. A note on the classical lower bound for a quantum walk algorithm.
quant-ph/0312230v1. Google Scholar - [32] . 1988. Are there interactive protocols for co-NP languages?Inform. Proc. Lett. 28 (1988), 249–251. Google ScholarDigital Library
- [33] . 1996. A fast quantum mechanical algorithm for database search. In Proc. ACM STOC. 212–219.
quant-ph/9605043. Google ScholarDigital Library - [34] . 2013. Quantum computation vs. Firewalls. J. High Energy Phys.85 (2013).
arXiv:1301.4504. Google Scholar - [35] . 2019. Limitations of semidefinite programs for separable states and entangled games. Commun. Math. Phys. 366, 2 (2019), 423–468.
arXiv:1612.09306. Google ScholarCross Ref - [36] . 2019. Induced subgraphs of hypercubes and a proof of the sensitivity conjecture. Ann. Math. 190, 3 (2019), 949–955.
arXiv:1907.00847. Google Scholar - [37] . 2007. Quantum and classical strong direct product theorems and optimal time-space tradeoffs. SIAM J. Comput. 36, 5 (2007), 1472–1493.
Earlier version in FOCS’04. quant-ph/0402123. Google ScholarDigital Library - [38] . 2021. The quantum supremacy tsirelson inequality. In Proc. Innovations in Theoretical Computer Science (ITCS’21). 1–13.
arXiv:2008.08721. Google Scholar - [39] . 2017. Quantum sampling problems, bosonsampling, and quantum supremacy. Npj Quantum Inf. 3, 15 (2017).
arXiv:1702.03061. Google Scholar - [40] . 2011. Component mixers and a hardness result for counterfeiting quantum money.
arXiv:1107.0321. Google Scholar - [41] . 2018. Classical verification of quantum computations. In Proc. IEEE FOCS. 259–267.
arXiv:1804.01082. Google Scholar - [42] . 2018. Quantum computing in the NISQ era and beyond.
arXiv:1801.00862. Google Scholar - [43] . 2019. Oracle separation of BQP and PH. In Proc. ACM STOC. 13–23.
ECCC TR18-107. Google ScholarDigital Library - [44] . 2011. Reflections for quantum query algorithms. In Proc. ACM-SIAM Symp. on Discrete Algorithms (SODA’11). 560–569.
arXiv:1005.1601. Google ScholarDigital Library - [45] . 1992. IP=PSPACE. J. ACM 39, 4 (1992), 869–877.
Earlier version in FOCS’90, pp. 11–15. Google ScholarDigital Library - [46] . 2021. An optimal separation of randomized and query complexity. In Proc. ACM STOC. 1289–1302.
arXiv:2008.10223. Google ScholarDigital Library - [47] . 1997. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26, 5 (1997), 1484–1509.
Earlier version in FOCS’94. quant-ph/9508027. Google ScholarDigital Library - [48] . 1994. On the power of quantum computation. In Proc. IEEE FOCS. 116–123. Google ScholarDigital Library
- [49] . 2020. Towards optimal separations between quantum and randomized query complexities. In Proc. IEEE FOCS. 228–239.
arXiv:1912.12561. Google Scholar
Index Terms
- Open Problems Related to Quantum Query Complexity
Recommendations
Exponential quantum speed-ups are generic
A central problem in quantum computation is to understand which quantum circuits are useful for exponential speed-ups over classical computation. We address this question in the setting of query complexity and show that for almost any sufficiently long ...
Nonadaptive quantum query complexity
We study the power of nonadaptive quantum query algorithms, which are algorithms whose queries to the input do not depend on the result of previous queries. First, we show that any bounded-error nonadaptive quantum query algorithm that computes a total ...
Polynomial degree vs. quantum query complexity
Special issue on FOCS 2003The degree of a polynomial representing (or approximating) a function f is a lower bound for the quantum query complexity of f. This observation has been a source of many lower bounds on quantum algorithms. It has been an open problem whether this lower ...
Comments