Why Turing Machines are Quantum

by noospheer

Quantum computing (QC) is a flexible model of computation and there are many physical means of implementing it. One obvious means of implementation is by classical simulation. In other words, performing QC by running ‘quantum software’ on conventional hardware.

Many believe that fundamentally new hardware must be designed in order to exploit the power of QC, such as this 7-qubit trapped ion QC. And while new scalable hardware is the end game for the field, it is not necessarily true that new hardware must be designed to achieve scalability. The question of whether Turing machines (classical computers) can efficiently emulate universal QC is entirely open. This problem is formally known as P vs BQP.

Noospheer argues that classical computers and quantum computers are polynomially equivalent (P = BQP), ie. that the device you’re reading this blog with is a scalable quantum device. We can make this argument based on a few, well accepted findings:

  1. Certain quantum gates (“Cliffords”) and certain quantum states (“stabilizers”) are classically efficient. This is shown by the well known/loved Gottesman-Knill theorem and has been tested in code with GraphSim and other software. Recently, this theorem was extended to include all “positive Wigner states”, which include both the stabilizer states and “bound” states.
  2. Clifford circuits plus a non-Clifford gate results in universal QC. Whereas the Gottesman-Knill theorem is sub-universal, the addition of a non-Clifford gate type to the GK theorem results in BQP computing (BQP = universal QC — the ability to run any linear quantum algorithm). Everyone wants BQP computers.
  3. As Bravyi and Kitaev showed in 2004, magic states allow for universal QC with only Clifford gates. Magic states are a special resource which can be consumed to apply the action of a non-Clifford gate in a Clifford-only circuit. However, since magic states are “pure, non-Pauli eigenstates”, they are slow to simulate classically.
  4. It is known that noise can be applied to make the action of universal QC circuits classically easy to simulate. However, when applying noise to a system, there must be some kind of error correction or the end result is erroneous.
  5. Quantum error correction (QEC) is typically performed at each gate, so if used in a classical simulation, noise will be removed as soon as it is applied, resulting in an inability to efficiently simulate the system. Therefore QEC must be applied at the end of computation in order to avoid exponential overhead as a result of correction. “Post-computation QEC” was previously thought hard, yet it has been recently shown that it is doable.

Therefore: Implement a Clifford circuit (easy). Use a classically prepared magic state to inject a non-Clifford gate (such as a T gate) into the circuit to achieve universality. Apply sufficient noise to turn the T gate output into an easy-to-simulate ‘barely negative’ bound state (states that have a very small amount of Wigner negativity) – avoiding slowdown. Repeat this process until the computation has evolved to completion. Finally, apply post-computation QEC to recover the error-free answer to your quantum question.


Classically efficient universal quantum circuit

In order to be proven, this result must be implemented as classical software. If successful, it will have applications ranging from cryptography to finance, energy, medical care and beyond.