4
$\begingroup$

The Gottesman-Knill theorem says that many circuits, including all Clifford curcuits can be simulated classically in polynomial time.

On the other hand it is believed that there is no polynomial time classical simulation of universal quantum computation.

Does there exist a (local?) gate-set which is non-universal and yet not known to be simulateable in polynomial time?

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ What do you mean with "local gate-set"? One-qubit gates? $\endgroup$
    – qubitzer
    Commented Jun 11 at 13:59
  • $\begingroup$ Please explain what you mean by "local". On the other hand, the set of Clifford gates is a non-universal polytime simulatable gate-set. However, it is not local in the sense that each gate acts on a single qubit as you need a two-qubit gate like CNOT (or CZ) to generate the full Cliffords. However, the Pauli gates are local in this sense, efficiently simulatable, and not universal. $\endgroup$
    – Condo
    Commented Jun 11 at 14:41
  • $\begingroup$ I mean gate sets that consists of 1 qubit gates and say 2, 3 or 4 qubit gates. $\endgroup$
    – Frederik Ravn Klausen
    Commented Jun 11 at 15:47
  • 1
    $\begingroup$ @Condo local gates is a very common term to refer to gates which have support on a constant number of qubits. See also local circuits etc. $\endgroup$
    – Markus Heinrich
    Commented Jun 12 at 9:20
  • 1
    $\begingroup$ @MarkusHeinrich Thanks! Indeed, it makes sense when you think about it for more than 5 seconds. My comment was made without enough thought. $\endgroup$
    – Condo
    Commented Jun 13 at 13:59

3 Answers 3

Reset to default
6
$\begingroup$

This is a commonly-asked question, whose answer is (I believe) still unknown even under standard complexity-separation conjectures like P$\ne$NP and BPP$\ne$BQP.

For example in "The Classification of Reversible Bit Operations" from 2015, Aaronson, Grier, and Schaffer (link to arXiv) list the key open problem of classifying all quantum circuits based on the gate-sets used.

This was even in Aaronson's 2005 posting on "The 10 Semi-Grand Challenges for Quantum Computing Theory" - with question 1 asking:

Also, is it true that every class of quantum gates is either universal for BQP, or else simulable in classical polynomial time? If so, what criterion separates the two? If not, do we get an interesting hierarchy of complexity classes between BPP and BQP?

Alternatively what we have learned is that there are certain restricted classes of quantum computing that might not be efficiently simulable classically - but might also not even capture all of what a classical computer can efficiently do! I'd refer to (1) IQP circuits, (2) DQC-1 circuits, and (3) BosonSampling linear optical circuits for examples of the above. These classes may contain problems outside of NP, but yet may not efficiently simulate every problem in P!

One thing that I've wondered about, but I haven't found a way to formalize, is that period-finding may not be in P but is in BQP and indeed is even in NP. For example, given an oracle $f$ with a promise that $f(x)=f(x+r)$ for some $r$, find $r$. This problem can be solved efficiently with a QFT, but also $r$ is an NP-certificate for a decision version of this problem. Thus oracularly this problem is in BQP and also in NP - which means, under the standard assumption that BQP$\not\subseteq$NP, it is somehow "sub-universal" for quantum computation.

Analogously people have studied a lot about "monotonic boolean functions" - circuits built solely out of AND and OR gates (without NOT gates). Satisfiability is efficiently solvable with such sets of gates.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Thank you, this is extremely illuminating. But my question is slightly different. I am not thinking about something that (under some complexity assumption) is provably not simulatable, but whether there is some set of gates which is neither known to be universal nor to be simulatable. $\endgroup$
    – Frederik Ravn Klausen
    Commented Jun 12 at 13:10
  • $\begingroup$ Every gate is classically simulatable - just not necessarily efficiently simulatable. If we don't care about efficiency we can just as easily run Schroedinger's equation to keep track of the entirety of the wavefunction after each gate (or update the path integral if we're interested in the amplitude of a particular basis). $\endgroup$
    – Mark Spinelli
    Commented Jun 12 at 13:56
  • 1
    $\begingroup$ There's no known class of gates that is "between" P and BQP, but there are "almost" classes such as instantaneous quantum polynomial-time circuits (IQP circuits). The set of gates there are limited to $\sqrt {CZ}$ and $R(\pi/4)$ gates - sampling from a circuit so-built that is sandwiched between Hadamard gates is not classically simuatable (unless some strange consequences related to the collapsing of the polynomial hierarchy occurs). $\endgroup$
    – Mark Spinelli
    Commented Jun 12 at 13:57
  • $\begingroup$ Not efficiently classically simulable. $\endgroup$
    – Mark Spinelli
    Commented Jun 12 at 20:11
6
$\begingroup$

I'm going to slightly reinterpret the question, because you cannot just talk about algorithms from gates. You have to talk about algorithms based on gates + initial states. For example, the simulation of stabilizer circuits in the Gottesman-Knill theorem is predicated on your starting state being a stabilizer state (such as the all 0s state).

So, is there a set of unitaries + initial states whose computational power is not know to be universal and not known to be efficiently simulatable? Yes. The model is called DQC-1. It is generally believed that it can solve some problems efficiently that classical computers cannot, and probably doesn't have the full power of a universal quantum computer (and may not even have the full power of a universal classical computer).

Improve this answer
$\endgroup$
2
  • $\begingroup$ I think it’s the same with IQP circuits? $\endgroup$
    – Mark Spinelli
    Commented Jun 13 at 12:33
  • $\begingroup$ @MarkSpinelli It may be, but I'm not so familiar with it. $\endgroup$
    – DaftWullie
    Commented Jun 13 at 13:33
0
$\begingroup$

I think it might really depend on how you define universal, you can argue $CCX$ and $H$ are not universal as you cannot obtain any states with complex amplitudes. But at the same time any quantum circuit has an equivalent circuit with only $CCX$ and $H$ gates so that shouldn't be classically simulable!

Improve this answer
$\endgroup$

Your Answer

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

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