The Quantum Graph

Tag: quantum

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…


Assumptions (tsk tsk)

Human beings like to make assumptions. Assumptions seem to make the world a less demanding place to understand. Ironically, no kind of human is more susceptible to falling prey to assumptions than the scientist. In the strict definition, a scientist prides him/herself on proof through rigorous observation of well-constructed experiments.

However, if a question is hard, it’s difficult to devise an experiment which can answer it. When this is the case, many scientists fall back on beliefs which they assume to be true. This is unfortunate, as the universe is mysterious, and assumptions generally turn out to be false (ex: “all heavenly bodies orbit the Earth”).

A modern scientific assumption is that factoring is hard. Factoring involves taking a number and determining which two prime numbers multiply together to equal the original number. For example, 21 factors into 3 times 7. Despite the simplicity of the problem, there is no obviously efficient way to solve it. So, if the original number is sufficiently large, a computer may take a billion years to get the answer. Due to its hardness, factorization is at the heart of public key cryptography (PKC).

PKC is responsible for keeping computer systems secure. Virtually all institutions encrypt data with PKC. Virtually all ‘secure’ online transactions and digital signatures rely on PKC for their relative security. Symmetric-key cryptography (SKC – using a secret key that cannot be guessed logically) doesn’t directly rely on PKC, but the problem with SKC keys is a critical requirement that they be shared by both parties. This implies a secure connection must be established in order to share the private key in the first place — unless you share the key off-network. Simply, SKC needs factoring to be hard too.

Shor’s quantum algorithm factors in polynomial time (fast). Thus, Shor’s discovery ruins current security systems. However, it is a quantum algorithm and requires a quantum computer. Recently, Shor’s algorithm was implemented on a quantum computer and succeeded in factoring the number 21 in polynomial time. However, PKC uses numbers much larger than 21. So, it would be interesting to see whether Shor’s algorithm can be efficiently implemented on a classical computer, such as an iPhone.

It is proven here and extended here, that at least one major component of Shor’s factorization algorithm – the quantum Fourier transform (QFT) – can run efficiently on classical computers. The harder part of Shor’s is something called modular exponentiation (ME), and this is commonly assumed to be an impossible task for classical computers. However, it is also now proven that ME can be broken down and reconstructed in terms of the QFT. Therefore, the totality of Shor’s algorithm can run on an iPhone. If you find this alarming, rest assured such a breakthrough brings QKD much closer to fruition.

There are deep subtleties in the papers cited above, which we are carefully investigating. Should our assumption that factoring is classically easy prove true, we will publish our findings here.

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.

Ghost in the Martian

Total Recall, 1990

Save the Moon landings, Mars Science Lab aka Curiosity is NASA’s crowning technical achievement. The complexity of its entry, descent and landing (EDL), the rugged capability of its large and flexible design, and high ingenuity of its instrumentation; all come together as a complete package for deep exploration of the Sun’s 4th planet. Mars is no longer such a distant frontier thanks to missions like this one.

With hardware that goes to other worlds, there come design challenges such as having to radiation-harden the computer. Since it currently takes many years to plan and build a robotic space probe, the processor and memory specs are well behind the cutting edge back here on Earth. MSL RCE (rover compute element) is equipped with two twin computers (1 as backup): 200MHz single-core processor, 256mb RAM, 2gb flash. The top data transfer rate between Earth and the rover via Mars reconnaissance orbiter (MRO) is 2mbits per second. All quite modest but still damn impressive given Mariner 4 returned a total of 634kb which included 22 images back in 1965.

The Mini Cooper-sized vehicle runs on a plutonium-powered generator that puts out 125 watts – for comparison, a mid-range computer power supply from your local hardware store will channel 5 times that!

Given that computational power and raw electricity are limited, the focus then becomes how you use it. The MSL software team writes and uploads new programs on a sol by sol basis, so the rover is not exactly autonomous – other than its hazard-avoidance capability. It faithfully goes exactly where Earth tells it and carries out precise instructions for imaging, surveying, sampling and so on. Given the one way time delay between Earth and Mars ranges from 4 to 22 minutes, controlling Curiosity presumably consists of sending over long, linear instructions.

As a software development outfit, Noo Corp has tasked itself with squeezing hidden potential out of typical computing hardware by emulating qubits. We recognize that the great challenges of modern computer science are relatively simple problems for quantum hardware. Therefore, writing classical code that takes efficient advantage of quantum math is the answer to many tough and important questions. Such questions include, ‘can Curiosity independently carry out advanced science with only general instructions from Earth?’ In other words, can software alone turbo boost the rover’s intelligence, and thereby transform her into a full blown scientist – not just a lowly researcher? 😉

We argue, ‘yes’.

Mars’ first closeup, 15 July 1965

Mission Updates

Classical Cat, Quantum Mouse

(12:15:11 PM) bradass87: hypothetical question: if you had free reign [sic] over classified networks for long periods of time … say, 8–9 months … and you saw incredible things, awful things … things that belonged in the public domain, and not on some server stored in a dark room in Washington DC … what would you do? […]

With the UK threatening to forcibly extricate Wikileaks‘ Julian Assange from the Ecuadorian embassy in London, its plain to see governments get… concerned, if state secrets become public domain.

When it comes to sensitive digital information, the world has relied on encryption for keeping secrets. The dominant encryption scheme is RSA, first made public in 1977. It relies on a hard problem: the fact that there is no known classical way to efficiently factor numbers. In other words, despite knowing how to do it, cracking RSA can take thousands of years with the current technique. However, in 1994, MIT mathematician/physicist Peter Shor showed that a quantum computer could factor numbers in polynomial time (milliseconds instead of millennia).

Lucky for the entities that use RSA to shield their data from prying eyes, there has yet to be a practical, scalable quantum computer and thus their data is safe for the time being.

Unfortunately or fortunately, depending on your side of the fence, it is only a matter of innovation (creativity + effort + time) before quantum computing is scalable and the world’s encrypted info is completely naked. Of course, the twist is that far stronger means of keeping data private have emerged in the quantum research space.

Whether you’re an individual who just wants their online activity to remain anonymous, or an agency with hard intelligence on a pending Martian invasion — don’t be too paranoid, but don’t delude yourself into believing security is forever.

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.