Quantum Computation


A quantum computer uses characteristic features of quantum mechanics to solve certain problems much faster than is possible with any classical computer. Typically information is stored via the various states of a suitable quantum system. Information processing can then be achieved by evolving the system in a controlled fashion according to the laws of quantum mechanics. Lastly measurement of appropriate observables gives a readout. This may not seem very different from any classical computation. But clever use of characteristic features of quantum mechanics such as superposition and entanglement provides a form of parallel information processing, which can in theory give vast speedups over any classical computation.

At the moment a handful of quantum algorithms which provide such advantages exist. The most celebrated is Shor's algorithm for the factorization of integers which gives an exponential speedup over its best known classical competitor. Grover's algorithm for an unstructured database search provides a quadratic speedup but has a potentially wider range of application. The Deutsch-Jozsa algorithm which addresses questions regarding global properties of a restricted class of Boolean functions is not as useful but does at least provide a good test bed for quantum computation. It has also been suggested that quantum computation may provide for the efficient simulation of quantum systems; in effect the quantum computer mimics the behavior of another quantum system of interest.

Quantum Computation was first suggested in the early 1980s and the first quantum algorithms appeared in the mid 1990s. These developments have stimulated research in the field to the point where a number of groups devote their entire research efforts to the subject. The theoretical foundations of quantum computation are already well advanced and the concepts of quantum gates, quantum algorithms, quantum Turing machines and quantum error correction are well established. The greatest challenge in the field is to construct a working quantum computer with an appreciable number of qubits. Current practical realizations are limited to a handful of qubits.

Expectation Value Quantum Computing

Quantum algorithms are usually formulated for execution on a quantum computer consisting of a single quantum system. The computation begins by initializing the system in a pure state and ends with a projective measurement, whose outcome yields a meaningful problem solution with good probability. In contrast the most successful experimental realizations of quantum algorithms to date have used room-temperature, solution state nuclear magnetic resonance (NMR). The NMR sample contains an ensemble of identical, non-interacting quantum computers. Such systems are in highly mixed states and measurements on these can only yield expectation values of observables, and not the standard projective measurement outcomes. Quantum algorithms have been modified accordingly. However, these modifications (e.g. pseudopure state preparation) have been designed to mimic the original algorithm as much as possible and have not used the ensemble to any advantage.

My current research focusses on these modifications. I recently demonstrated that it is possible to use the ensemble to speed up Grover's search algorithm on an expectation value quantum computers (see Phys. Rev. A. 65, 052321 (2002)). The speedup is by a factor independent of the database size and depends on measurement resolution.

NMR Realization of the Deutsch-Jozsa algorithm

NMR has become a favorite tool for demonstrating the dynamics of quantum computation. While working at North Carolina State University, I lead an experimental NMR implementation of the Deutsch-Jozsa algorithm for functions with three bit arguments. We showed that it is at this level that characteristic features of quantum mechanics first become essential in the algorithm. We used the three carbon spins of  13C labeled alanine (CH3CH(HN2)CO2H) for qubits and successfully applied the algorithm to a representative of each class of balanced functions at this level (see Phys. Rev. A 62, 022304 (2000)). More details can be found in the preprint quant-ph/9910006. Output spectra for representatives of each function class are available via the following links:

  f1(x2,x1,x0) = x2  f1 spectrum (PostScript)
  f2(x2,x1,x0) = x2 + x1  f2 spectrum (PostScript)
  f3(x2,x1,x0) = x2 + x1 + x0  f3 spectrum (Postscript)
  f4(x2,x1,x0) = x2x1 + x0  f4 spectrum (PostScript)
  f5(x2,x1,x0) = x2 x1 + x2 + x0  f5 spectrum (PostScript)
  f6(x2,x1,x0) = x2 x1 + x2 + x1 + x0  f6 spectrum (PostScript)
  f7(x2,x1,x0) = x2 x1 + x1 x0 + x2 + x1  f7 spectrum (PostScript)
  f8(x2,x1,x0) = x2 x1 + x1 x0 + x2  f8 spectrum (PostScript)
  f9(x2,x1,x0) = x2 x1 + x1 x0 + x2 x0  f9 spectrum (PostScript)
  f10(x2,x1,x0)= x2 x1 + x1 x0 + x2 x0 + x1 + x0  f10 spectrum (PostScript)

Our implementation incorporated an "indirect" realization of a two qubit gate between two spins, using a chain of couplings between the spins rather than the "direct" realization which uses only the coupling between the spins. Such indirect gate realizations are expected to become indispensable for quantum computation as the number of qubits increases.

Quantum Computation Publications

  1. Brandon M. Anderson and David Collins, "Polarization Requirements for Ensemble Implementations of Quantum Algorithms with a Single Bit Output," Phys. Rev. A 72, 042337 (2005). Preprint quant-ph/0508061.
  2. Arvind and David Collins, "Scaling issues in ensemble implementations of the Deutsch-Jozsa algorithm," Phys. Rev. A 68, 052301 (2003). Preprint quant-ph/0307153.
  3. David Collins, "Shortening Grover's search algorithm for an expectation value quantum computer," Preprint quant-ph/0209148. Submitted to the proceedings of QCMC'02 (2002).
  4. David Collins, "Modified Grover's algorithm for an expectation-value quantum computer," Phys. Rev. A. 65, 052321 (2002). Preprint quant-ph/0111108.
  5. David Collins, K. W. Kim, W. C. Holton, H. Sierzputowska-Gracz, E. O. Stejskal, "Orchestrating an NMR quantum computation: the N=3 Deutsch-Jozsa algorithm," Preprint quant-ph/0105045 (2001).
  6. David Collins, K. W. Kim, W. C. Holton, H Sierzputowska-Grazc, and E. O. Stejskal, "NMR quantum computation with indirectly coupled gates," Phys. Rev. A 62, 022304 (2000).
  7. David Collins, K. W. Kim, and W. C. Holton, "Deutsch-Jozsa algorithm as a test of quantum computation," Phys Rev A, 58, 1633 (1998).

Selected Conference Presentations and Posters

  1. "Scaling Issues in Ensemble Quantum Algorithms," Poster presented at the Quantum Information and Quantum Control Conference, Fields Institute, Toronto, July 19-23, 2004.  Postscript  Pdf
  2. "Could Quantum Computing Aid Path Integration?," MSRI conference, Berkeley, California, December 2002.  Postscript  Pdf
  3. "Shortening Grover's Search Algorithm for an Expectation Value Quantum Computer," Poster presented at the 6th International Conference on Quantum Communication, Measurement and Computing, MIT, Cambridge, Massachusetts, July 2002.  Postscript
  4. "NMR Quantum Computation with Indirectly Coupled Gates," Poster presented at the 41st Experimental Nuclear Magnetic Conference, Pacific Grove, California, 2000.  Postscript

Invited Talks

  1. "Quantum Computing with Ensembles: Strange Physics for Ordinary Tasks," April 2006.   Pdf
  2. "Quantum Computing with Ensembles," Talk at Bucknell University, November 2005.   Pdf

Functional Integration


  1. David Collins, "Two-State Quantum Systems Interacting with Their Environments: A Functional Integral Approach," PhD thesis, University of Texas at Austin, (December 1997).  (Postscript available on request)