<p>One easy way to come up with such a model is to first create a restricted model of quantum computation that can still do something non-classical, and then just give it classical computation for free.</p>

<p>An examples of this strategy is the one clean qubit model (along with a BPP machine). Some references: <a href="http://arxiv.org/abs/quant-ph/9802037">On the Power of One Bit of Quantum Information</a>, <a href="http://arxiv.org/abs/quant-ph/0608132">Computation with Unitaries and One Pure Qubit</a> and <a href="http://arxiv.org/abs/0707.2831">Estimating Jones polynomials is a complete problem for one clean qubit</a>.</p>

<p>Another example would be to have a log-depth (or polylog depth) quantum circuit with access to a classical computer. This will yield something like $BPP^{BQNC}$.</p>

CC BY-SA 3.0
2011-11-25T07:34:51.550Z
This certainly works for computational complexity, but does it work for query complexity? I don't immediately see any problem for which the one clean qubit model + BPP yields better query complexity than a classical machine. Also, in general this technique can fail, since giving a Clifford group or match gate computer classical computation boosts them to universal quantum computation.
Joe Fitzsimons
CC BY-SA 3.0
2011-11-25T15:36:35.667Z
@JoeFitzsimons: I can't think of a problem off the top of my head, but I think Dan Shepherd shows an oracle separation between BPP and the one clean qubit model in his paper. Your second point is valid, of course.
Robin Kothari
CC BY-SA 3.0
2011-11-25T19:34:09.323Z
But surely an oracle separation does not necessarily imply a query complexity separation.
Joe Fitzsimons
CC BY-SA 3.0
2011-11-26T04:13:48.007Z
I agree with @JoeFitzsimons, although the DQC1 model is interesting, I haven't seen a query complexity separation for it. The natural problems like trace estimation or Peter Shor's variant of the Jones polynomial problem seem hard to present in the query model.
Artem Kaznatcheev
CC BY-SA 3.0
2011-11-24T21:47:41.113Z
2011-11-24T21:47:41.113Z
Robin Kothari
<p>Not really a full answer, but if you are prepared to loosen the constraint that $X(f)\leq D(f)$ (or $R_2(f)$), then one answer would seem to be a quantum computer restricted to the Clifford group computation. Such a machine can implement the Deutsch algorithm, and hence can be seperated from the classical case, and can trivially be simulated by a full quantum machine. However, such a machine is not computationally universal, and so there are some query functions (such as computing the AND of the output of an oracle) which it simply cannot perform.</p>

CC BY-SA 3.0
2011-11-25T00:39:23.650Z
This is in some sense an interesting case. Clifford group computations are simulate not only in $\mathsf P$, but in polylog depth as a result if containment in $\oplus L$. So unrelativised, one would never describe it as being intermediate between "classical" and "quantum"; maybe between $\mathsf P$ and $\mathsf L$. Only when the non-computational-basis states obtained from Clifford operations are acted on by the (unsimulatable because unknown) oracle does the extension beyond the simply classical give you any advantage.
Niel de Beaudrap
CC BY-SA 3.0
2011-11-24T16:43:48.887Z
2011-11-24T16:43:48.887Z
Joe Fitzsimons
<p>Maybe the more clear example of this kind of computing models is DQC1 explained by @RobinKothari in his answer. See the references in his answer for a good introduction to the model.</p>

<p>Also, rather recently, there was a nice article in Nature magazine about Quantum Discord. Quantum Discord is a information-theoretic measure of non-classical correlations, generalizing entanglement. Here's the <a href="http://www.nature.com/news/2011/110601/full/474024a.html" rel="nofollow noreferrer">link</a>. You'll see there that there are examples of computations where entanglement doesn't play a fundamental role, i.e., other non-classical correlations are the ones taking care of speeding-up the computation. This happens in DQC1 for computing the trace of a matrix (see the paper by <a href="http://arxiv.org/abs/0709.0548" rel="nofollow noreferrer">Datta, Shaji, and Caves</a>). What's interesting in the article is that it opens the question on "Quantum Discord based algorithms", i.e., algorithms where you don't need entanglement for quantum speed-up. That's something between full quantum computation and classical.</p>

<p>Another model that possibly fall in this category (between full-quantum and classical) is the Linear Optical Model by Arkhipov and Aaronson. See <a href="https://cstheory.stackexchange.com/questions/2892/how-does-the-bosonsampling-paper-avoid-easy-classes-of-complex-matrices">this question</a> for a nice explanation.</p>

<p>I don't know where these models fit in terms of query complexity, but could be a good starting point.</p>

CC BY-SA 3.0
2011-11-25T00:48:56.237Z
2011-11-25T00:48:56.237Z
2017-04-13T12:32:28.080Z
Marcos Villagra
<p>It is well known quantum computers are strictly more powerful than their classical counterparts in terms of <a href="http://cstheory.blogoverflow.com/2011/07/quantum-query-complexity/" rel="nofollow noreferrer">query complexity</a>. </p>

<blockquote>
  <p>Are there other models (natural or artificial) that are strictly between the quantum and classical in terms of query complexity? </p>
</blockquote>

<p>The seperation can be on</p>

<ul>
<li>specific problems: model X computes function $f$ with strictly more queries than quantum, but fewer queries than the lower bound on classic, or</li>
<li>different problems: model X computes function $f_1$ with strictly more queries than quantum, but computes function $f_2$ with fewer queries than classical. </li>
</ul>

<p>In both cases, we want for every function $f$ to have $Q_2(f) \leq X(f) \leq R_2(f)$ to avoid examples that are hard to compare to quantum (like the <a href="https://cstheory.stackexchange.com/q/5380/1037">certificate complexity</a> of non-deterministic queries). Here $Q_2(f)$ (and $R_2(f)$) is the two-sided $1/3$-error quantum (and classical randomized) query complexity and the inequalities are within constant factors.</p>

<cc.complexity-theory><quantum-computing><query-complexity>
Models of computation strictly between classical and quantum in terms of query complexity
Artem Kaznatcheev
# Models of computation strictly between classical and quantum in terms of query complexity

(Asked by: username_0 on 2011-11-24)

It is well known quantum computers are strictly more powerful than their classical counterparts in terms of [query complexity](http://cstheory.blogoverflow.com/2011/07/quantum-query-complexity/).

> Are there other models (natural or artificial) that are strictly between the quantum and classical in terms of query complexity?

The seperation can be on

* specific problems: model X computes function $f$ with strictly more queries than quantum, but fewer queries than the lower bound on classic, or
* different problems: model X computes function $f\_1$ with strictly more queries than quantum, but computes function $f\_2$ with fewer queries than classical.

In both cases, we want for every function $f$ to have $Q\_2(f) \leq X(f) \leq R\_2(f)$ to avoid examples that are hard to compare to quantum (like the [certificate complexity](https://cstheory.stackexchange.com/q/5380/1037) of non-deterministic queries). Here $Q\_2(f)$ (and $R\_2(f)$) is the two-sided $1/3$-error quantum (and classical randomized) query complexity and the inequalities are within constant factors.

**Tags:** cc.complexity-theory, quantum-computing, query-complexity

---

## 3 answers

### Answer by username_1 on 2011-11-24. Score: 9

One easy way to come up with such a model is to first create a restricted model of quantum computation that can still do something non-classical, and then just give it classical computation for free.

An examples of this strategy is the one clean qubit model (along with a BPP machine). Some references: [On the Power of One Bit of Quantum Information](http://arxiv.org/abs/quant-ph/9802037), [Computation with Unitaries and One Pure Qubit](http://arxiv.org/abs/quant-ph/0608132) and [Estimating Jones polynomials is a complete problem for one clean qubit](http://arxiv.org/abs/0707.2831).

Another example would be to have a log-depth (or polylog depth) quantum circuit with access to a classical computer. This will yield something like $BPP^{BQNC}$.

> **Comments:**
> **username_2**: This certainly works for computational complexity, but does it work for query complexity? I don't immediately see any problem for which the one clean qubit model + BPP yields better query complexity than a classical machine. Also, in general this technique can fail, since giving a Clifford group or match gate computer classical computation boosts them to universal quantum computation.  
> **username_1**: @JoeFitzsimons: I can't think of a problem off the top of my head, but I think Dan Shepherd shows an oracle separation between BPP and the one clean qubit model in his paper. Your second point is valid, of course.  
> **username_2**: But surely an oracle separation does not necessarily imply a query complexity separation.  
> **username_0**: I agree with @JoeFitzsimons, although the DQC1 model is interesting, I haven't seen a query complexity separation for it. The natural problems like trace estimation or Peter Shor's variant of the Jones polynomial problem seem hard to present in the query model.  

---

### Answer by username_2 on 2011-11-24. Score: 7

Not really a full answer, but if you are prepared to loosen the constraint that $X(f)\leq D(f)$ (or $R\_2(f)$), then one answer would seem to be a quantum computer restricted to the Clifford group computation. Such a machine can implement the Deutsch algorithm, and hence can be seperated from the classical case, and can trivially be simulated by a full quantum machine. However, such a machine is not computationally universal, and so there are some query functions (such as computing the AND of the output of an oracle) which it simply cannot perform.

> **Comments:**
> **username_3**: This is in some sense an interesting case. Clifford group computations are simulate not only in $\mathsf P$, but in polylog depth as a result if containment in $\oplus L$. So unrelativised, one would never describe it as being intermediate between "classical" and "quantum"; maybe between $\mathsf P$ and $\mathsf L$. Only when the non-computational-basis states obtained from Clifford operations are acted on by the (unsimulatable because unknown) oracle does the extension beyond the simply classical give you any advantage.  

---

### Answer by username_4 on 2011-11-25. Score: 2

Maybe the more clear example of this kind of computing models is DQC1 explained by @RobinKothari in his answer. See the references in his answer for a good introduction to the model.

Also, rather recently, there was a nice article in Nature magazine about Quantum Discord. Quantum Discord is a information-theoretic measure of non-classical correlations, generalizing entanglement. Here's the [link](http://www.nature.com/news/2011/110601/full/474024a.html). You'll see there that there are examples of computations where entanglement doesn't play a fundamental role, i.e., other non-classical correlations are the ones taking care of speeding-up the computation. This happens in DQC1 for computing the trace of a matrix (see the paper by [Datta, Shaji, and Caves](http://arxiv.org/abs/0709.0548)). What's interesting in the article is that it opens the question on "Quantum Discord based algorithms", i.e., algorithms where you don't need entanglement for quantum speed-up. That's something between full quantum computation and classical.

Another model that possibly fall in this category (between full-quantum and classical) is the Linear Optical Model by Arkhipov and Aaronson. See [this question](https://cstheory.stackexchange.com/questions/2892/how-does-the-bosonsampling-paper-avoid-easy-classes-of-complex-matrices) for a nice explanation.

I don't know where these models fit in terms of query complexity, but could be a good starting point.


---

