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. http://arxiv.org/abs/1212.0506


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…