2
$\begingroup$

Question

Aaronson wrote in his thesis that

“essentially all quantum algorithms that we know today—from Shor’s algorithm, as discussed previously, to Grover’s algorithm, to the quantum adiabatic algorithm, to the algorithms of Hallgren and van Dam, Hallgren, and Ip—are oracle algorithms at their core. We do not know of any non-relativizing quantum algorithm technique analogous to the arithmetization technique that was used to prove PSPACE ⊆ IP. If such a technique is ever discovered, I will be one of the first to want to learn it.”

The common quantum algorithms I know of can be all explained using black-box model (i.e., query model):

Grover's search. An $O(\sqrt{n})$-query algorithm that computes the OR of $n$ bits.

Shor's algorithm. The kernel, Shor's period finding algorithm, is an $O({\rm poly} \log n)$-query algorithm that computes the period of a function, given its truth table as an $n$-bit input.

There are more examples like quantum local search and quantum-walk-based algorithms.

Do we have any problem that admits a quantum speedup, which cannot be explained using black-box model at present?

Meaning of this question

The quantum query complexity of any partial Boolean function is completely characterized by the general adversary bound (see e.g. [LMR+11]), which is a natural method, in the sense of Razborov and Rudich. If it turns out that every quantum technique relativizes, I think we will have some very interesting insight on quantum computing, from a computational complexity aspect.

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ Can you be any more precise about what you mean by "explained using black-box model"? Shor's factoring algorithm doesn't require a black-box setting; it can be understand as an algorithm that takes an integer as input and outputs a non-trivial factor of it. $\endgroup$ – D.W. Oct 24 at 20:25
  • $\begingroup$ @D.W. Yes, that is one kind of understanding. Likewise, Grover’s search can be understand as an $O(2^{n/2} m^{O(1)})$-time algorithm for SAT. By “explained using black-box model” I mean “that quantum algorithm, and its advantage compared to a classical one, can be realized in the black-box query model. $\endgroup$ – Lwins Oct 24 at 20:33
  • 2
    $\begingroup$ Every algorithm can be realized in a black-box model by not making any queries to the black box. I guess I'm not seeing how to make this notion precise. $\endgroup$ – D.W. Oct 24 at 22:16
  • 1
    $\begingroup$ One could say the operation of an algorithm can be 'explained using a black box' if one input is a function and the only thing the algorithm does is execute the function at bounded cost. In particular, it does not access any circuit description of the function, and does not make any assumption of the size of such description. In a white-box model, the opposite is true: Accessing the circuit description and a bound on its size is at the core of such an algorithm. $\endgroup$ – Martin Schwarz Dec 3 at 12:40
  • 1
    $\begingroup$ E.g. the Feynman-Kitaev Hamiltonian. A unitary represented as a poly-sized quantum circuit (white box) can be mapped efficiently into a Local Hamiltonian useful for adiabatic QC, but not an arbitrary (black-box) unitary. $\endgroup$ – Martin Schwarz Dec 3 at 12:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.