Quantum factorization algorithm by NMR ensemble computers

Daxiu Wei, Xiaodong Yang, J. L. Luo +2 more

Noboru Kunihiro, Shigeru Yamashita

No polynomial time algorithms have been proposed for the factoring and discrete logarithm problems.However, Shor showed that these problems can be solved by aquantum Turing machine in 1994.Sev- eral devices have been proposed toward the realization of quantum computers.Among them, the NMR quantum computer seems to be the nearest to the target goal.Since the NMR quantum computer has different features from ordinary ones, we cannot directly implement Shor's algorithms.In this paper, we propose new simple algorithms that work on NMR quantum computers to solve the factoring and discrete logarithm problems.

Ivan S. Oliveira, Tito José Bonagamba, Roberto S. Sarthour +2 more

P. Oscar Boykin, Tal Mor, Vwani Roychowdhury +1 more

In ensemble (or bulk) quantum computation, all computations are performed on an ensemble of computers rather than on a single computer. Measurements of qubits in an individual computer cannot be performed; instead, only expectation values (over the complete ensemble of computers) can be measured. As a result of this limitation on the model of computation, many algorithms cannot be processed directly on such computers, and must be modified, as the common strategy of delaying the measurements usually does not resolve this ensemble-measurement problem. Here we present several new strategies for resolving this problem. Based on these strategies we provide new versions of some of the most important quantum algorithms, versions that are suitable for implementing on ensemble quantum computers, e.g., on liquid NMR quantum computers. These algorithms are Shor's factorization algorithm, Grover's search algorithm (with several marked items), and an algorithm for quantum fault-tolerant computation. The first two algorithms are simply modified using a randomizing and a sorting strategies. For the last algorithm, we develop a classical-quantum hybrid strategy for removing measurements. We use it to present a novel quantum fault-tolerant scheme. More explicitly, we present schemes for fault-tolerant measurement-free implementation of Toffoli and σ(z)(¼) as these operations cannot be implemented "bitwise", and their standard fault-tolerant implementations require measurement.

Jonathan A. Jones

Tetsuro Nishino

In 1985, David Deutsch introduced quantum Turing machines (QTMs for short) as Turing machines which can perform so called quantum parallel computations. Algorithms executed on QTMs are called quantum algorithms. It is well known that Peter Shor designed a polynomial time quantum algorithm for integer factoring in 1994. In this paper, we first illustrate several major methods of designing efficient quantum algorithms with Shor's algorithm as an example. On the other hand, many researchers are studying how to physically implement quantum computers based on QTM. Among others, NMR (Nuclear Magnetic Resonance) offers an appealing prospect for implementation of quantum computers because of a number of reasons. But, quantum computations performed on NMR is slightly different from those performed on QTMs. For example, Shor's factoring algorithm cannot be executed on an NMR quantum computer as it is. In this paper, we show how to factor integers in polynomial time by using NMR quantum computers.