<h2>Question</h2>

<p>Aaronson wrote in his <a href="https://arxiv.org/pdf/quant-ph/0412143.pdf#page45" rel="nofollow noreferrer">thesis</a> that</p>

<blockquote>
  <p>“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.”</p>
</blockquote>

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

<p><strong>Grover's search.</strong> An <span class="math-container">$O(\sqrt{n})$</span>-query algorithm that computes the OR of <span class="math-container">$n$</span> bits.</p>

<p><strong>Shor's algorithm.</strong> The kernel, <em>Shor's period finding algorithm</em>, is an <span class="math-container">$O({\rm poly} \log n)$</span>-query algorithm that computes the period of a function, given its truth table as an <span class="math-container">$n$</span>-bit input.</p>

<p>There are more examples like quantum local search and quantum-walk-based algorithms.</p>

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

<h2>Meaning of this question</h2>

<p>The quantum query complexity of any partial Boolean function is completely characterized by the general adversary bound (see e.g. <a href="https://arxiv.org/pdf/1011.3020" rel="nofollow noreferrer">[LMR+11]</a>), which is a <em>natural</em> 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.</p>

CC BY-SA 4.0
2019-10-24T20:25:33.097Z
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.
D.W.
CC BY-SA 4.0
2019-10-24T20:33:40.927Z
@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.
Lwins
CC BY-SA 4.0
2019-10-24T22:16:46.037Z
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.
D.W.
CC BY-SA 4.0
2019-10-25T03:45:30.143Z
@D.W. I don’t know how to make it precise either... That’s why I put some examples and hope it helps.
Lwins
CC BY-SA 4.0
2019-12-01T03:34:30.810Z
Define relativizing and non-relativizing quantum techniques please.
Turbo
CC BY-SA 4.0
2019-12-03T12:40:05.123Z
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.
Martin Schwarz
CC BY-SA 4.0
2019-12-03T12:40:26.717Z
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.
Martin Schwarz
CC BY-SA 4.0
2022-01-26T05:48:43.117Z
How about boson sampling (a term that I believe was coined by Aaronson himself), or [Gibbs sampling](https://link.springer.com/article/10.1007/s00220-016-2641-8)? The paragraph that you quoted said that the technique used to prove PSPACE ⊆ IP was the type of technique he was looking for: much later than the publication of that thesis, it was proven that QIP = PSPACE, do you know if any techniques from there were the type you're seeking?
user1271772
<soft-question><quantum-computing>
Quantum advantage beyond the black-box model
Lwins
# Quantum advantage beyond the black-box model

(Asked by: username_0 on 2019-10-24)

## Question

Aaronson wrote in his [thesis](https://arxiv.org/pdf/quant-ph/0412143.pdf#page45) 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]](https://arxiv.org/pdf/1011.3020)), 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.

**Tags:** soft-question, quantum-computing

> **Comments:**
> **username_1**: 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.  
> **username_0**: @username_1 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.  
> **username_1**: 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.  
> **username_0**: @username_1 I don’t know how to make it precise either... That’s why I put some examples and hope it helps.  
> **username_2**: Define relativizing and non-relativizing quantum techniques please.  
> **username_3**: 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.  
> **username_3**: 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.  
> **username_4**: How about boson sampling (a term that I believe was coined by Aaronson himself), or [Gibbs sampling](https://link.springer.com/article/10.1007/s00220-016-2641-8)? The paragraph that you quoted said that the technique used to prove PSPACE ⊆ IP was the type of technique he was looking for: much later than the publication of that thesis, it was proven that QIP = PSPACE, do you know if any techniques from there were the type you're seeking?  

---

## 0 answers

