CoChat
Sign Up
Cited by 558Quantum Computing Algorithms and ArchitectureQuantum Information and CryptographyQuantum Mechanics and Applications

Implementation of a quantum search algorithm on a quantum computer

Open access
Jones, Jonathan A., Mosca, Michele, Hansen, Rasmus H.·1998·Nature
DOI 10.1038/30687
Open this paper in CoChat — free accountOpen PDF

Abstract

In 1982 Feynman observed that quantum-mechanical systems have an information-processing capability much greater than that of corresponding classical systems, and could thus potentially be used to implement a new type of powerful computer. Three years later Deutsch described a quantum-mechanical Turing machine, showing that quantum computers could indeed be constructed. Since then there has been extensive research in this field, but although the theory is fairly well understood, actually building a quantum computer has proved extremely difficult. Only two methods have been used to demonstrate quantum logic gates: ion traps, and nuclear magnetic resonance (NMR),. NMR quantum computers have recently been used to solve a simple quantum algorithm—the two-bit Deutsch problem,. Here we show experimentally that such a computer can be used to implement a non-trivial fast quantum search algorithm initially developed by Grover,, which can be conducted faster than a comparable search on a classical computer.

AI snapshot

Written from the paper’s full text.

TL;DR

The paper reports an experimental implementation of Grover’s quantum search algorithm on a two-qubit nuclear magnetic resonance (NMR) quantum computer. For a two-bit domain with one satisfying element, the quantum search found the element with one function evaluation, while a classical search would require between 1 and 3 evaluations.

Key findings

  • The algorithm was implemented using two 1H nuclear spins in partially deuterated cytosine as the two qubits.
  • For each of the four possible functions \(f_{ab}\) with a unique satisfying element, the NMR spectra showed the computer largely ended in the expected final state \(|ab\rangle\).
  • The two-bit quantum search required only one function evaluation, compared with 1 to 3 evaluations for a classical search of the same domain.
  • Small but significant errors appeared as distortions in the final spectra, and these distortions were particularly bad for the function \(f_{01}\).

Methods

  • Two-qubit NMR quantum computer: two spin states of 1H nuclei in a magnetic field served as qubits, with radio frequency fields and spin-spin couplings used to implement quantum logic gates.
  • The quantum circuit used pseudo-Hadamard gates implemented by 90° y pulses, a function-evaluation gate \(U_{f_{ab}}\) implemented by the pulse sequence in Fig. 2, and a final \(U_{00}\) gate identical to \(U_{f_{00}}\).
  • An effective pure state was created using methods of Cory et al.; measurement was performed by an additional 90° pulse and observing NMR signal phases, with a reference spectrum from a 90° pulse on the initial state and a magnetic field gradient pulse before detection to dephase error terms.

Limitations

  • Stated: it is not practical to begin in a true \(|00\rangle\) state with an NMR quantum computer, so an effective pure state was used; it is also not practical to determine the final state directly, and absolute NMR phases cannot be interpreted without a reference signal.
  • Stated: the most significant errors arose from the NMR pulse sequence, especially selective pulses intended to affect one spin while leaving the other unaffected; distortions varied and were particularly bad for \(f_{01}\).
  • Evident from the text: the demonstration is limited to a two-qubit system searching a four-element domain with a unique satisfying element, so it does not itself demonstrate scaling to larger searches.

Model-written summary. Check it against the paper before relying on it.

Integrity signals

Registry

Crossref · 10.1038/30687

Cites

5 of 5 references verified0 citation errors · 0 not checkable

Statistics

Nothing to recompute.

Claims the paper makes

0 of 15 cited sources checked · 0 supported · 0 flagged

  • Findingown data
    § Implementation of a Quantum Search Algorithm on a Nuclear Magnetic Resonance Quantum Computer · p. 3

    The distortions are particularly bad in the spectrum obtained when the function is f_01.

    “Interestingly the distortions are much worse in some cases than in others: they are particularly bad in the spectrum obtained when the function is f 01 .”
    Quote in the paperNot a substantial claim
  • Findingown data
    § Implementation of a Quantum Search Algorithm on a Nuclear Magnetic Resonance Quantum Computer · p. 1

    The authors implemented a quantum search algorithm (Grover's) on a two-qubit NMR quantum computer.

    “Here we show how such a computer can be used to implement a fast quantum search algorithm initially developed by Grover. 9, 10”
    • Also stated in: § Implementation of a Quantum Search Algorithm on a Nuclear Magnetic Resonance Quantum Computer · p. 2 · plain
      “This algorithm was implemented using our two qubit NMR quantum computer, described in Ref. 7.”
    Quote in the paperSubstantial claim0 of 2 sources checked
    • cites [9] Grover, L. K. in Proc. 28th Annual ACM Symp. on Theory of Computation 212–218 (ACM, New York, (1996)). source

      Not checked in the free run.

    • cites [10] Grover, L. K. Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett. 79, 325–328 (1997). source

      Not checked in the free run.

  • Premisecitation
    § Implementation of a Quantum Search Algorithm on a Nuclear Magnetic Resonance Quantum Computer · p. 1

    Grover's algorithms enable an extremely rapid search over the domain of a binary function to find elements for which the function is satisfied.

    “Among other applications Grover's algorithms enable an extremely rapid search over the domain of a binary function to find elements for which this function is satisfied (that is, the function has the value 1).”
    Quote in the paperSubstantial claim0 of 2 sources checked
    • cites [9] Grover, L. K. in Proc. 28th Annual ACM Symp. on Theory of Computation 212–218 (ACM, New York, (1996)). source

      Not checked in the free run.

    • cites [10] Grover, L. K. Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett. 79, 325–328 (1997). source

      Not checked in the free run.

  • Premisecitation
    § Implementation of a Quantum Search Algorithm on a Nuclear Magnetic Resonance Quantum Computer · p. 2

    Using the methods of Cory et al., it is possible to create an effective pure state that behaves equivalently to |00>.

    “Using the methods of Cory et al. 5 it is, however, possible to create an effective pure state, which behaves in an equivalent manner.”
    Quote in the paperSubstantial claim0 of 1 sources checked
    • cites [5] Cory, D. G., Fahmy, A. F. & Havel, T. F. Ensemble quantum computing by NMR spectroscopy. Proc. Natl Acad. Sci. USA 94, 1634–1639 (1997). source

      Not checked in the free run.

    • Rests on an assumption: It is not practical to begin in a true |00> state with an NMR quantum computer.
  • Interpretationreasoning
    § Implementation of a Quantum Search Algorithm on a Nuclear Magnetic Resonance Quantum Computer · p. 3

    The most significant cause of errors is errors in the NMR pulse sequence used to implement the calculation.

    “These errors arise from a variety of causes, but the most significant is errors in the NMR pulse sequence used to implement the calculation.”
    Quote in the paperNot a substantial claim
  • May combine two claims. 8
  • Classified as probably not a substantial claim. 4

  • May combine two claims.

    Findingreasoning
    § Implementation of a Quantum Search Algorithm on a Nuclear Magnetic Resonance Quantum Computer · p. 3

    Most distortions are removed by the field gradient pulse, but their effects remain visible as variations in the heights of the NMR lines.

    “While most of these distortions are removed by the field gradient pulse, their effects remain visible as variations in the heights of the NMR lines.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Findingreasoning
    § Implementation of a Quantum Search Algorithm on a Nuclear Magnetic Resonance Quantum Computer · p. 3

    There are small but significant errors in the calculation, resulting in distortions in the final spectra.

    “There are however small but significant errors in the calculation, which result in distortions in the final spectra.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Premisecitation
    § Implementation of a Quantum Search Algorithm on a Nuclear Magnetic Resonance Quantum Computer · p. 2

    In general, searching a domain of size N for one of k satisfying elements requires about 1/2 (N/k) function evaluations classically, while quantum search requires only O(√(N/k)).

    “In the more general case of searching a domain of size N for one of k satisfying elements the classical search requires about 1 2 ( N/k ) function evaluations, while the quantum search 11 requires only O ( √ N/k ).”
    Quote in the paperSubstantial claim0 of 1 sources checked
    • cites [11] Boyer, M., Brassard, G., Høyer, P. & Tapp, A. in Proc. 4th Workshop on Physics and Computation—PhysComp '96 (eds Toffoli, T., Biafore, M. & Leão, J.) 36–41 (New England Complex Systems Institute, Boston, MA, (1996)).

      Not checked in the free run.

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Study design and conductown data
    § Implementation of a Quantum Search Algorithm on a Nuclear Magnetic Resonance Quantum Computer · p. 2

    The final 90° detection pulse was preceded by a magnetic field gradient pulse to dephase the majority of any error terms.

    “To improve the appearance of the spectra the final 90 ◦ detection pulse was preceded by a magnetic field gradient pulse, which acts to dephase the majority of any error terms which might occur.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Premisenone given
    § Implementation of a Quantum Search Algorithm on a Nuclear Magnetic Resonance Quantum Computer · p. 3

    The pulse sequences require a large number of selective pulses, which only affect one of the two spins making up the computer.

    “These pulse sequences require a large number of selective pulses, that is pulses which only affect one of the two spins making up the computer.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Premisecitation
    § Implementation of a Quantum Search Algorithm on a Nuclear Magnetic Resonance Quantum Computer · p. 2

    The algorithm uses a single function evaluation to label the single state which satisfies the function, followed by a series of gates which drive the system into this particular state.

    “This algorithm uses a single function evaluation to label the single state which satisfies the function, followed by a series of gates which drive the system into this particular state.”
    Quote in the paperSubstantial claim0 of 2 sources checked
    • cites [9] Grover, L. K. in Proc. 28th Annual ACM Symp. on Theory of Computation 212–218 (ACM, New York, (1996)). source

      Not checked in the free run.

    • cites [10] Grover, L. K. Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett. 79, 325–328 (1997). source

      Not checked in the free run.

  • May combine two claims.

    Interpretationreasoning
    § Implementation of a Quantum Search Algorithm on a Nuclear Magnetic Resonance Quantum Computer · p. 3

    In practice it is difficult to achieve the desired effect at one spin while leaving the other entirely unaffected, resulting in errors in the final result.

    “In practice it is difficult to achieve the desired effect at one spin while leaving the other entirely unaffected, resulting in errors in the final result.”
    Quote in the paperSubstantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Premisecitation
    § Implementation of a Quantum Search Algorithm on a Nuclear Magnetic Resonance Quantum Computer · p. 1

    Only two methods have been used to demonstrate quantum logic gates: ion traps and nuclear magnetic resonance (NMR).

    “only two methods have been used to demonstrate quantum logic gates: ion traps, 3, 4 and nuclear magnetic resonance (NMR). 5, 6”
    Quote in the paperNot a substantial claim0 of 4 sources checked
    • cites [3] Cirac, J. I. & Zoller, P. Quantum computations with cold trapped ions. Phys. Rev. Lett. 74, 4091–4094 (1995). source

      Not checked in the free run.

    • cites [4] Monroe, C., Meekhof, D. M., King, B. E., Itano, W. M. & Wineland, D. J. Demonstration of a fundamental quantum logic gate. Phys. Rev. Lett. 75, 4714–4715 (1995). source

      Not checked in the free run.

    • cites [5] Cory, D. G., Fahmy, A. F. & Havel, T. F. Ensemble quantum computing by NMR spectroscopy. Proc. Natl Acad. Sci. USA 94, 1634–1639 (1997). source

      Not checked in the free run.

    • cites [6] Gershenfeld, N. A. & Chuang, I. L. Bulk spin-resonance quantum computation. Science 275, 350–356 (1997). source

      Not checked in the free run.

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Premisecitation
    § Implementation of a Quantum Search Algorithm on a Nuclear Magnetic Resonance Quantum Computer · p. 1

    NMR quantum computers have previously been used to demonstrate quantum algorithms to solve the two bit Deutsch problem.

    “NMR quantum computers have previously been used to demonstrate quantum algorithms to solve the two bit Deutsch problem. 7, 8”
    Quote in the paperNot a substantial claim0 of 2 sources checked
    • cites [7] Jones, J. A. & Mosca, M. Implementation of a quantum algorithm to solve Deutsch's problem on a nuclear magnetic resonance quantum computer. J. Chem. Phys. (in the press); also LANL preprint quant-ph/9801027.

      Not checked in the free run.

    • cites [8] Chuang, I. L., Vandersypen, L. M. K., Zhou, X., Leung, D. W. & Lloyd, S. Experimental realization of a quantum algorithm. Nature 393, 143–146 (1998); also LANL preprint quant-ph/9801037. source

      Not checked in the free run.

  • Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

    Premisecitation
    § Implementation of a Quantum Search Algorithm on a Nuclear Magnetic Resonance Quantum Computer · p. 1

    The approach is simpler if the number of satisfying values is known beforehand, and is particularly simple when precisely one quarter of the elements in the domain satisfy the function.

    “This approach is simpler if the number of satisfying values is known beforehand, and is particularly simple when precisely one quarter of the elements in the domain satisfy the function. 11”
    Quote in the paperNot a substantial claim0 of 1 sources checked
    • cites [11] Boyer, M., Brassard, G., Høyer, P. & Tapp, A. in Proc. 4th Workshop on Physics and Computation—PhysComp '96 (eds Toffoli, T., Biafore, M. & Leão, J.) 36–41 (New England Complex Systems Institute, Boston, MA, (1996)).

      Not checked in the free run.

  • May combine two claims.

    Premisereasoning
    § Implementation of a Quantum Search Algorithm on a Nuclear Magnetic Resonance Quantum Computer · p. 1

    A classical search of a two-bit domain requires between 1 and 3 evaluations of the function to find the satisfying element, while a quantum search can find this element with only one function evaluation.

    “A classical search of this domain would require between 1 and 3 evaluations of the function to find the satisfying element, while a quantum search can find this element with only one function evaluation.”
    Quote in the paperSubstantial claim
11 of 11

  • The paper relies on this without support.

    It is not practical to begin in a true |00> state with an NMR quantum computer.

    “The algorithm should start with the computer in state | 00 〉 , but with an NMR quantum computer it is not practical to begin in a true | 00 〉 state.”

  • The paper relies on this without support.

    It is not practical to determine the final state directly with an NMR quantum computer.

    “Similarly it is not practical to determine the final state directly, but an equivalent measurement can be made by exciting the spin system with a further 90 ◦ pulse, and observing the phases of the resulting NMR signals.”

  • The paper relies on this without support.

    The absolute phase of an NMR signal depends in a complex manner on experimental details, so absolute phases cannot be interpreted.

    “The absolute phase of an NMR signal depends in a complex manner on a variety of experimental details, and so it is not possible to interpret absolute phases, but this can be overcome by measuring a reference signal, obtained by applying a 90 ◦ pulse directly to the initial state.”
3 of 3

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Prototype quantum computers that store and process information on individual atoms have already been demonstrated.

    “Although an Avogadro scale computer that can act on 10 23 bits might seem implausible, prototype quantum computers that store and process information on individual atoms have already been demonstrated 64 -65 , 76 -80 .”

    From Ultimate physical limits to computation (2000) · cites this paper as [79]

  • Recently constructed quantum microcomputers use one quantum degree of freedom for each bit and operate at the Heisenberg limit Δt = π hbar/2ΔE for the time needed to flip a bit.

    “The laws of physics do not require redundancy to perform logical operations: recently constructed quantum microcomputers use one quantum degree of freedom for each bit and operate at the Heisenberg limit ∆ t = π ¯ h/ 2∆ E for the time needed to flip a bit 64 -65 , 76 -80 .”

    From Ultimate physical limits to computation (2000) · cites this paper as [79]

  • Contemporary quantum microcomputers constructed using nuclear magnetic resonance operate at the limits of speed and memory space described above.

    “In fact, contemporary quantum 'microcomputers' such as those constructed using nuclear magnetic resonance 76 -80 do indeed operate at the limits of speed and memory space described above.”

    From Ultimate physical limits to computation (2000) · cites this paper as [79]

Cites

Flagged first, then by citations

Research works printed but not linked: 8

  1. Monroe, C., Meekhof, D. M., King, B. E., Itano, W. M. & Wineland, D. J. Demonstration of a fundamental quantum logic gate. Phys. Rev. Lett. 75, 4714–4715 (1995). · DOI · Paper page
  2. Cory, D. G., Fahmy, A. F. & Havel, T. F. Ensemble quantum computing by NMR spectroscopy. Proc. Natl Acad. Sci. USA 94, 1634–1639 (1997). · DOI · Paper page
  3. Gershenfeld, N. A. & Chuang, I. L. Bulk spin-resonance quantum computation. Science 275, 350–356 (1997). · DOI · Paper page
  4. Jones, J. A. & Mosca, M. Implementation of a quantum algorithm to solve Deutsch's problem on a nuclear magnetic resonance quantum computer. J. Chem. Phys. (in the press); also LANL preprint quant-ph/9801027. · arXiv
  5. Chuang, I. L., Vandersypen, L. M. K., Zhou, X., Leung, D. W. & Lloyd, S. Experimental realization of a quantum algorithm. Nature 393, 143–146 (1998); also LANL preprint quant-ph/9801037. · DOI · Paper page
  6. Boyer, M., Brassard, G., Høyer, P. & Tapp, A. in Proc. 4th Workshop on Physics and Computation—PhysComp '96 (eds Toffoli, T., Biafore, M. & Leão, J.) 36–41 (New England Complex Systems Institute, Boston, MA, (1996)).
  7. Chuang, I. L., Gershenfeld, N. & Kubinec, M. Experimental implementation of fast quantum searching. Phys. Rev. Lett. 80, 3408–3411 (1998). · DOI · Paper page
  8. Laflamme, R., Knill, E., Zurek, W. H., Catasti, P. & Mariappan, S. V. S. NMR GHZ Proc. R. Soc. Lond. A (in the press). · DOI

Cited by

Sorted by citations

Authors
Jones, J. A., Mosca, M., & Hansen, R. H.
Affiliations
University of Oxford (GB)
Corresponding author
Jones, Jonathan A.
ORCID
Venue
Nature
Publisher
Springer Science and Business Media LLC
Published
1998-05
Volume
393
Issue
6683
Pages
344-346
ISSN
  • 0028-0836 (ISSN-L)
  • 1476-4687
DOI
10.1038/30687
OpenAlex
W2582029817
Semantic Scholar
5d5a66beeabde6b5288073320b7ad09e3b64812a
Cited by
558
References
5
Citations by year
2026: 2 · 2025: 13 · 2024: 16 · 2023: 12 · 2022: 17 · 2021: 22 · 2020: 12 · 2019: 12 · 2018: 16 · 2017: 14 · 2016: 23 · 2015: 14 · 2014: 9 · 2013: 6 · 2012: 13
FWCI
52.00
Type
journal article
Language
en
Open access
Licence
www.springer.com/tdm (unspecified)
Locations
  • Nature (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • RePEc: Research Papers in Economics (submittedVersion)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Mechanics and Applications
Keywords
quantum search, Grover's algorithm, NMR quantum computing, nuclear magnetic resonance, quantum gates, quantum computing

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Claims read by deepseek-v4.1-flash under definition version 3 (extract-v3) on 2026-10-06.

Classified by jev-1.13-20260917 (gold-guideline-v0.2) on 2026-10-06.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review