An efficient quantum algorithm is proposed to solve in polynomial time the parity problem, one of the hardest problems both in conventional quantum computation and in classical computation, on NMR quantum computers. It is based on the quantum parallelism principle in a quantum ensemble, the selective decoherence manipulation, and the NMR phase-sensitive measurement. The quantum circuit for the quantum algorithm is designed explicitly.
An efficient quantum algorithm is proposed to solve in polynomial time the parity problem, one of the hardest problems both in conventional quantum computation and in classical computation, on NMR quantum computers. It is based on the quantum parallelism principle in a quantum ensemble, the selective decoherence manipulation, and the NMR phase-sensitive measurement. The quantum circuit for the quantum algorithm is designed explicitly.
The quantum search problem is an important problem due to the fact that a general NP problem can be solved efficiently by an unsorted quantum search algorithm. Here it has been shown that the quantum search problem could be solved in polynomial time on an NMR quantum computer. The NMR ensemble quantum computation is based on the quantum mechanical unitary dynamics that both a closed quantum system and its ensemble obey the same quantum mechanical unitary dynamics instead of on the pseudopure state or the effective pure state of the classical NMR quantum computation. Based on the new principle the conventional NMR multiple-quantum spectroscopy has been developed to solve experimentally the search problem. The solution information of the search problem is first loaded on the unitary evolution propagator which is constructed with the oracle unitary operation and oracle-independent unitary operations and is used to excite the multiple-quantum coherence in a spin ensemble. Then the multiple- quantum spectroscopy is used to extract experimentally the solution information. It has been discussed how to enhance the output NMR signal of the quantum search NMR multiple-quantum pulse sequence and some approaches to enhancing the NMR signal are also proposed. The present work could be helpful for conventional high field NMR machines to solve efficiently the quantum search problem.
A quantum computer (QC) can operate in parallel on all its possible inputs at once, but the amount of information that can be extracted from the result is limited by the phenomenon of wave function collapse. We present a new computational model, which differs from a QC only in that the result of a measurement is the expectation value of the observable, rather than a random eigenvalue thereof. Such an expectation value QC can solve nondeterministic polynomial-time complete problems in polynomial time. This observation is significant precisely because the computational model can be realized, to a certain extent, by NMR spectroscopy on macroscopic ensembles of quantum spins, namely molecules in a test tube. This is made possible by identifying a manifold of statistical spin states, called pseudo-pure states, the mathematical description of which is isomorphic to that of an isolated spin system. The result is a novel NMR computer that can be programmed much like a QC, but in other respects more closely resembles a DNA computer. Most notably, when applied to intractable combinatorial problems, an NMR computer can use an amount of sample, rather than time, which grows exponentially with the size of the problem. Although NMR computers will be limited by current technology to exhaustive searches over only 15 to 20 bits, searches over as much as 50 bits are in principle possible, and more advanced algorithms could greatly extend the range of applicability of such machines.
Quantum computers are able to operate on coherent superpositions of states, and to isolate a single global property of the set of computed quantities via interference. In principle, this permits them to solve certain problems exponentially faster thana classical computer, but not one has yet succeeded in implementing a true quantum computer on more than two quantum bits. Recently, however, it has been found that an ensemble of independent and identical quantum computers can perform mots of the same feats than a single quantum computer could, while at the same time bringing massive classical parallelism to bear on its computations. Such an ensemble quantum computer can be realized, to a limited extent, by nuclear magnetic resonance (NMR) spectroscopy on ordinary liquids at room temperature and pressure. This simple implementation depends on special kinds of mixed states, called pseudo-pure states, whose preparation entails a loss of signal that is exponential in the number of spins. While this would appear to limit such an implementation to ca. 8-10 spins in the foreseeable future, NMR spectroscopy has now permitted the first experimental demonstrations of all the basic features of quantum computing. We claim, moreover, that the product operator formalism, on which the theory of NM R spectroscopy is based, provides an efficient framework within which to analyze algorithms and decoherence effects in quantum computing more generally. This is illustrated by presenting our recent experimentally implementation of a quantum error correcting code.
The determination of the parity of a string of N binary digits is a well-known problem in classical as well as quantum information processing, which can be formulated as an oracle problem. It has been established that quantum algorithms require at least N∕2 oracle calls. We present an algorithm that reaches this lower bound and is also optimal in terms of additional gate operations required. We discuss its application to pure and mixed states. Since it can be applied directly to thermal states, it does not suffer from signal loss associated with pseudo-pure-state preparation. For ensemble quantum computers, the number of oracle calls can be further reduced by a factor 2k, with k∊1,2,…,log2(N∕2), provided the signal-to-noise ratio is sufficiently high. This additional speed-up is linked to (classical) parallelism of the ensemble quantum computer. Experimental realizations are demonstrated on a liquid-state NMR quantum computer.
A quantum computer is a device that processes information in a quantum-mechanically coherent fashion. In principle, it can exploit coherent quantum interference and entanglement to perform computations, such as factoring large numbers or searching an unsorted database, more rapidly than classical computers. Noise, decoherence, and manufacturing problems make constructing large scale quantum computers difficult. Ion traps and optical cavities offer promising experimental approaches, but no quantum algorithm has yet been implemented with those systems. On the other hand, because of their natural isolation from the environment, nuclear spins are particularly good 'quantum bits', and their use for quantum computation is possible by applying nuclear magnetic resonance (NMR) techniques in an unconventional manner. Here, we report on the experimental implementation of a quantum algorithm using NMR to solve a purely mathematical problem in fewer steps than is possible classically. Our simple quantum computer can determine the type of an unknown function using fewer function 'calls' than is possible using a classical computer.
Quantum algorithms are known for providing more efficient solutions to certain computational tasks than any corresponding classical algorithm. Here we show that a single qudit is sufficient to implement an oracle based quantum algorithm, which can solve a black-box problem faster than any classical algorithm. For 2d permutation functions defined on a set of d elements, deciding whether a given permutation is even or odd, requires evaluation of the function for at least two elements. We demonstrate that a quantum circuit with a single qudit can determine the parity of the permutation with only one evaluation of the function. Our algorithm provides an example for quantum computation without entanglement since it makes use of the pure state of a qudit. We also present an experimental realization of the proposed quantum algorithm with a quadrupolar nuclear magnetic resonance using a single four-level quantum system, i.e., a ququart.