Classically efficient universal quantum computation (P=BQP) with magic and bound states

Question

$\text P$ vs $\text {BQP}$ is an open question. That is, "can systems which require a polynomial number of qubits in the size of an input be described with only a polynomial number of bits?" If the answer is "yes", then the device you're reading this with can factor quickly and do other fun things, whoopee! Most quantum information scientists assume that universal quantum computation is hard for Turing machines / classical computers, but there is no proof to show classical computers are quantum-weak. We know the following:

• Clifford circuits acting on stabilizer states are classically efficient (Gottesman-Knill theorem).
• All quantum states with a positive Wigner representation are classically efficient. This includes both stabilizer states and so-called bound states (see here). Bound states are interesting because they cannot be described trivially as combinations of stabilizer states (they lie outside the stabilizer polytope / octahedron), yet are still easy to classically simulate.
• Magic states promote Clifford circuits to full quantum universality by allowing for the application of a non-Clifford unitary through a process called 'gate teleportation' or 'gate injection' (see here). Magic states however, being pure non-stabilizer states are classically inefficient to simulate.
• It has been shown that if one can simulate a reusable magic state, then quantum power is classically realizable with software which takes advantage of the finding, ie. $\text P = \text{BQP}$ (see here). This is a big finding, but magic states are generally destroyed in the teleport/injection process so it seems hard to achieve magic-state-reusability.

The reason why $\text P$ becomes $\text{BQP}$ when the magic state is reusable is because the number of terms introduced by the magic state is kept constant; whereas in the typical magic state scenario (where the magic state is destroyed during gate injection), the number of terms grows exponentially with each magic state introduced to the computation (generally $N$ magic states consumed per $N$ non-Clifford transformations required, so $d^N$ terms).

Thus the challenge then becomes: how can we keep the number of terms constant but not be burdened with devising an invincible magic state? Ie. how can we employ a linear number of magic states in our simulation but keep the terms introduced by such states constant as in the $\text{P}=\text{BQP}$ finding from this article.

The proposed answer to the above problem is to compress the output of the gate injection qudit to the nearest 0 / neutral Wigner state (Wigner representations in this context are defined in this paper in the middle of p.5). Specifically, the gate injection circuit has 2 inputs: an info input $|\psi \rangle$, and a magic state $|T\rangle$. The output is the result state of a $T$ gate applied to $\psi$, $T|\psi\rangle$. In the event the output $T|\psi\rangle$ has a negative (inefficient) Wigner representation, we would then compress that qudit so that its state is shifted to the nearest 0 Wigner representation.

Your thought may be, well, the quantumness will be lost when you shift the output of the gate injection circuit to the nearest 0 Wigner state. But wait! 0 is neither a positive nor negative number, so we are not technically shifting it to a positive (weak and fast) state, but a neutral state -- by contrast, negative states are strong but seemingly slow. This is potentially an important distinction because while such 0 Wigner states are efficiently simulable, they may also retain quantum power.

The bottom line is we would have a circuit with Clifford gates, positive and neutral Wigner states (the latter sometimes called zero-sum-negative states), and unlimited use of magic states -- with the caveat that the output of the gate injection circuit can never be negative, and if so it must be shifted to the nearest 0/neutral Wigner state. Is such a system universal for QC?

Answer 1

I think the problem could be to do with your distinction of positive and zero/neutral Wigner states. I believe that the best way to understand the statement in this paper is as follows: For simplicity consider a single qudit state $\rho$, then this state has a positive Wigner representation if $W_{\rho}(\boldsymbol{u})\ge0 \forall\boldsymbol{u\in\mathbb{Z}_{d}^{2}}$ --- notice the equality sign. This should be interpreted as that all states with $W_{\rho}(\boldsymbol{u})\ge0 +\epsilon$ s.t. $\epsilon\rightarrow0$, are positive Wigner states, and hence all such states can be classically efficiently simulated. Therefore, there is no ambiguity. (Edit 1: note that I am referring to some of the entries of the Wigner distribution to be $0$---the sum of the entries add up to 1. )

In contrast, states with $W_{\rho}(\boldsymbol{u})<0$, are negative. Whether all such states are useful resource states for magic state distillation is still unknown. In other words, is there a tight boundary between states that are efficiently simulatable and the resource states for magic states distillation? This question has been partially answered in the qubit case, where all the states above the edges of the stabilizer octahedron can be used to distil the H-type magic states as shown by Reichardt in this paper. (Aside: If I remember correctly, in the qubit case the region of states defined by the Veitch et al Wigner function coincide with stabilizer region, but I could be wrong). Whether there are more no-go theorems that rule out more mixed-states regions in the qudit case is still unknown. (Note: I hate taking limits, so I hope I didn't mess up the above results of Veitch et al)

Getting back to your question, if you replace the output state (after the gate is injection) with the nearest 0 Wigner state, then as far as we known such a state could only be non-classical (hard to simulate classically) if $W_{\rho}(\boldsymbol{u})<0$, and if such a state is known to be a useful resource for magic states distillation (i.e. if there exists a magic state protocol that distils magic states from such input state). Otherwise if $W_{\rho}(\boldsymbol{u})\ge0$, then the simulation will be completely classical. Also, shifting the output state to such a negative (0) state, is equivalent to applying a very noisy non-Clifford gate, which will cause the output of the simulation to be highly inaccurate, this is why magic state distillation is often used to derive upper-bounds thresholds for fault-tolerant quantum computation.

Answer 2

Qudits (d level quantum systems) of odd dimension are shown to have a 'physical' region of unknown power [fig 2., Anwar et al]. This region lies between the magic distillable states - known to be sufficient for universal quantum computation [Bravyi et al.]; and the classically efficient bound [Emerson et al.] and stabilizer states [Gottesman et al].

Anwar and I have in person recently discussed one disruptive hypothesis $[N]$: under certain conditions, this terra incognita (physical region in fig. 2) reflects the properties of its neighbors (both classical simulability and quantum universality). Investigation requires running these physical states through untested stabilizer correction codes and determining whether such systems evolve toward purity (universal) or mixedness (sub-universal). Further, in order to satisfy $[N]$, the physical/unknown states must be Wigner-positive and thus 'Turing-easy'. Some may be so within a curved Wigner-Weyl-Moyal quasiprobability distribution [Fischer et al].

A confirmation of the above implies collapse of the polynomial hierarchy.