Quantum computation with commuting operations

Abstract

Introduction Quantum physics has changed our world dramatically, from Laser pointers in our hand to our understanding of black holes. However, it is only lately that people start to ask whether quantum mechanics can be employed to make better computers or other information processing instruments. Around 1980, Richard Feynman and other scientists [1, 2] started to consider the possibility of using quantum computers to simulate interacting quantum systems, since in general it takes exponentially many coefficients to describe a many body system, which makes simulating quantum systems on a classical computer an infeasible task. In 1994, Peter Shor shows that quantum computers can factor integers much faster then any known classical algorithm [3], which also breaks a widely used cryptography protocol on the Internet. After that, quantum computing starts to attract people's interest, and physicists have spent huge efforts to build a quantum computer. Many different experimental implementations have been proposed, by using ion traps [4], superconducting circuits [5], etc. However, so far, only very small quantum computers have been built, which can achieve tasks like factoring 15 into 3 × 5 (see, for example [6]). Besides the practical aspect, there is another reason that makes quantum computing interesting. Before quantum computation was known, evidences were pointing to the direction that there is no physical machine able to do computation substantially faster than an electronic computer (more exactly, a Turing machine). This is the so called " extended Church-Turing thesis " (also called " strong Church-Turing " thesis, see [7]). Note that the conjecture is rather about physical laws, and has very similar spirit as thermodynamic laws. Thus if we prove quantum computers can outperform classical ones, then we have to abandon our long-time belief; otherwise we will have more faith in it. There are also some interesting results on deriving physical laws from the computational power aspect. For example, it was shown in [8] that certain kinds of non-linearity in quantum mechanics would drastically increase its computational power, thus considered to be unlikely. However, it turns out that it is very difficult to characterize the power of quantum computers. For example, while the quantum algorithm for factoring performs exponentially faster than the best available classical algorithm, it is extremely hard to prove this for every possible classical algorithm. Indeed, if we can prove there is a (decision) problem which can be efficiently solved by quantum computers but not by …