18
$\begingroup$

It is well known quantum computers are strictly more powerful than their classical counterparts in terms of 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 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.

Improve this question
$\endgroup$

3 Answers 3

Reset to default
8
$\begingroup$

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, Computation with Unitaries and One Pure Qubit and Estimating Jones polynomials is a complete problem for one clean qubit.

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}$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Joe Fitzsimons
    Nov 25, 2011 at 7:34
  • $\begingroup$ @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. $\endgroup$
    – Robin Kothari
    Nov 25, 2011 at 15:36
  • $\begingroup$ But surely an oracle separation does not necessarily imply a query complexity separation. $\endgroup$
    – Joe Fitzsimons
    Nov 25, 2011 at 19:34
  • $\begingroup$ 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. $\endgroup$
    – Artem Kaznatcheev ♦
    Nov 26, 2011 at 4:13
7
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$
    – Niel de Beaudrap
    Nov 25, 2011 at 0:39
2
$\begingroup$

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. 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). 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 for a nice explanation.

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.