The Quantum Graph

Tag: turing

Why Turing Machines are Quantum

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.


On the power of Turing machines: Random notes from the quantum information community


Over the last year and half, I (Jordan Ash) have had correspondence with many quantum information students, postdocs, faculty, government personnel and business people at institutions around the world. Noospheer’s short term goal is to code a piece of software which allows for efficient, universal quantum computation using classical hardware. Here are snippets of those conversations.

Basically, the majority of quantum information people are in agreement with Mr. Chips:



Thanks for your interest in our paper.


I would like to know something more about your project.


Would it be possible to state a formal problem?


I’m afraid I’m not an expert on complexity classes and hence I am unable to evaluate your work.


Simulation of Quantum systems on conventional computers is a classical problem.


Suppose such a simulation was achieved.


I follow the logic of your claim


This sounds like a challenging project for the quantum computing community.


I would be interested to hear more about it.


What is the objective of your approach? Is it to show that any quantum evolution (so in particular any quantum computation) can be efficiently simulated classically?


Got it, will take a look.


From what you’ve told me, graduate school would be good times for you. If you’re serious about your project, I think a phd working towards it would straiten things out.


I wish you the very best of luck with this, it sounds exciting.


The best known general classical simulations of quantum computations take exponential time (if you want the correct answer with high probability or with certainty). To be practical, you would need a polynomial-time simulation, and there is an enormous gap between polynomial time and exponential time. Many very smart researchers have thought about the problem, and nobody has uncovered any evidence to suggest that arbitrary quantum computations can be simulated classically with less than exponential time overhead. Thus the default is to assume that it’s not doable. The basic issue is that a quantum computation can have exponentially many computation paths which are all maintained implicitly on a quantum computer (if one is ever actually built), but a classical computer would essentially need to keep track of all these paths explicitly.


My take is that [it from bit] all depends on the misconception that information is a logically prior concept to the laws of physics. The reverse is the case.


I think you are mistaken, and the basic unit of information in our world is the qubit and not the bit – but of course, this is just my opinion.


Good luck, though.


I wish you good luck with your project.


We would love to hear more about your emulations as they develop.


I don’t think this is likely to be a fruitful direction — to run quantum algorithms, you need to have a quantum computer.


I stopped working on quantum computing many years ago.


I’m not the person to talk to regarding the logic of the argument: my initial reaction is skeptical, since various smart people have been pursuing these ideas for two decades or more; someone like Daniel Gottesman or Richard Cleve at Waterloo might well be able to either point out a fallacy or confirm the importance of your work much more reliably than me.


There are a number of different potential methods of classical simulation of a quantum system, and the exponential factors enter into different places in different types of simulations.


The commuting circuit setting is an example where the choice of measurement drastically affects the hardness of classical simulations.


The global phase depends on the measurement results.


Your white paper was reviewed against the published criteria – we do NOT recommend that it be expanded into a full proposal.


Sounds like some interesting work.


You’re right of course that there is no room for belief when there is a mathematical proof. […] If you can prove P=BQP it would be an amazing accomplishment, almost as big a deal as P=NP.


Go ahead, implement it, use it to factor 1000-digit numbers and break the RSA cryptosystem, and become world-famous!


Also, somewhat surprisingly, factoring represents one of the few known cases of a problem that is known to be in the complexity class NP but is not NP complete.  Therefore, even if an efficient classical algorithm is found for factoring then there would be no consequences for complexity theory because it would not show that P is the same as NP.


I guess you could try to advertise on various QI sites, e.g. Quantiki.


Suddenly, A Wild Chess Game Appears.






Doesn’t white win after the first step?


To be honest I think that the argument is very trivial, i.e. a direct extension of the GK theorem.


The point of magic states is that they enable one to teleport a non-Clifford gate using only Clifford gates and the magic state.


In some sense, if a magic state is stored classically then it is automatically reusable; just store it in memory. But the decoding is still a problem.


Any state can be converted into any other state by some series of gates.


If you have a universal gate set, then I think any state will enable UQC.


By a perfect computation space you mean no noise?


Thanks for the clarification!


I myself am interested in building classical computer software for simulating quantum systems from both academic and business perspectives (in addition to my professorial activities, I have two companies, one of them devoted to developing scientific software.)


Good luck with your effort. People trying new things is what drives progress.


I was skimming the arxiv and thought this might be relevant.


Anyway, I hope you can get funding and start your business soon and I am always looking forward to work with you.


You will have to wait for the paper, it’s complicated to explain…


Collapsing the Polynomial Hierarchy is ‘Dangerous’

Not only is P vs. NP the defining question of our field; it’s one of the deepest questions ever asked for which we’d know how to recognize an answer. (In other words, one of the deepest questions in NP.)

Aaronson, p.1

quantum relic

A rigorous and therefore undeniable mathematical proof demonstrating a collapse of the polynomial hierarchy (PH) has a large number of big implications for the world beyond math and science.

  1. First, in terms of math and science; a successfully collapsed PH is closely related to efficient classical emulation of quantum systems (via post-IQP circuitry); in other words, regular computers may be fully capable of being quantum computers. The mainstream understanding — as alluded to in the post-IQP paper — is the rather naive one that quantum computation requires processors which demonstrate quantum effects as we currently define them. The mainstream is missing the point: computer science is, at its core, linguistics. If we know the math (which we do quite well), and assuming the Church-Turing thesis is actually universal, then we just need to teach our machines how to run the calculations (by writing insanely great code). One is now free to imagine a planet (such as this one) suddenly bustling with quantum computers, which include your laptops, cell phones and satellites. tada! [For the skeptic: W, X, Y, Z, 1, 2, 3 (pIQP demands a linear sample rate for PH collapse) It is also important to note that a collapse of the PH does not necessarily imply P = NP, however the two are inextricably related and are both considered ‘improbable’]
  2. What about our institutions/ourselves — specifically with regard to information privacy? The only factor which maintains a state of separation among entities in a shared space is unshared data. That said, with 1. in mind, the first thing a security guy/gal might consider is a ubiquitous encryption method called RSA being compromised. [Fun Fact: RSA was published 7 years after P v NP was formalized.]  Long story short, if 1. becomes a reality, then the invincible armor shielding governmental, financial, corporate, and an increasing amount of personal data from ‘adversaries’ — suddenly meets Kryptonite.Please consider this another early public WARNING: Any software we write which runs Shor’s factoring algorithm (or any QA) in polynomial time (efficiently) may likely render some encryption methods crackable, and will be published and distributed as a proof under language outlined in the Free Berkeley Software Distribution license.
  3. 2. outlines the atomic tip of the iceberg. Implications for medicine, energy, and time travel abound as well.

Dangerous, or benign? Probably both.

What is QC?

Non-physicists often have the mistaken idea that quantum mechanics is hard. Unfortunately, many physicists have done nothing to correct that idea. But in newer textbooks, courses, and survey articles, the truth is starting to come out: if you wish to understand the central ‘paradoxes’ of quantum mechanics, together with almost the entire body of research on quantum information and computing, then you do not need to know anything about wave-particle duality, ultraviolet catastrophes, Planck’s constant, atomic spectra, boson-fermion statistics, or even Schrödinger’s equation.

Aaronson 2004 p.23

‘Quantum computing’ sounds as exotic to physicists and computer scientists as it does to laypeople. The standard definition is that this is a field devoted to applying findings from the physics of quantum mechanics to computing in general. What is quantum mechanics? A mystical and apparently accurate description of the Cosmos that shows everything as ultimately everywhere at once. A lapis philosophorum.

Being fringey, quantum is mysterious. Yet, the mostly established assumption is that QC is an impossible task for a ‘classical’ computer/Turing machine – such as the device you’re reading this with. It requires intelligent management of exponentially complex resources. In other words, good old fashioned software is not capable of instructing a computer to carry out QC efficiently.

Thus classical implementation of QC is impractical and in order to overcome the problems, research facilities have started building exotic processors. This new class of hardware represents the beginnings of a fresh generation of technology. As it becomes scalable, we are left with the question: what will we do with all the obsolete classical hardware (laptops, desktops, servers, phones, satellites… ) we’ll have lying around?

Noospheer is engaged in the research/application of QC to permissive-license software which can run on any computer and faithfully reproduce live quantum systems — we’re attempting to successfully defy the assumption. This with goals of improving database search speeds, privacy and energy efficiency.

We’ll publish when ready for all the hackers.