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

Experimental Demonstration of a Compiled Version of Shor’s Algorithm with Quantum Entanglement

Open access
Lanyon, B. P., Weinhold, T. J., Langford, N. K., Barbieri, M., James, D. F. V., Gilchrist, A., White, A. G.·2007·Physical Review Letters
DOI 10.1103/physrevlett.99.250505
Open this paper in CoChat — free accountOpen PDF

Abstract

Shor's powerful quantum algorithm for factoring represents a major challenge in quantum computation. Here, we implement a compiled version in a photonic system. For the first time, we demonstrate the core processes, coherent control, and resultant entangled states required in a full-scale implementation. These are necessary steps on the path towards scalable quantum computing. Our results highlight that the algorithm performance is not the same as that of the underlying quantum circuit and stress the importance of developing techniques for characterizing quantum algorithms.

AI snapshot

Written from the paper’s full text.

TL;DR

The paper experimentally implements compiled order-finding circuits for Shor’s algorithm factoring \(N=15\) with \(C=2\) and \(C=4\), using photonic qubits and measurement-induced nonlinearity. It reports near-ideal algorithm outputs but substantially lower circuit/process fidelities, highlighting that algorithm performance is not the same as underlying circuit performance.

Key findings

  • The order-2 circuit gave logical probabilities \(\{P_{00},P_{10}\}=\{52,48\}\pm3\%\), and the order-4 circuit gave \(\{P_{000},P_{010},P_{100},P_{110}\}=\{27,23,24,27\}\pm2\%\); after classical processing, half the time the routines yield \(r=2\) or \(r=4\), giving factors 3 and 5.
  • Argument-register state fidelities were \(F=99.9\pm0.3\%\) for order-2 and \(F=98.5\pm0.6\%\) for order-4, with linear entropies \(SL=100\pm1\%\) and \(SL=98.1\pm0.8\%\), respectively.
  • Post-modular-exponentiation entangled states showed lower circuit performance: order-2 GHZ fidelity \(F_{\mathrm{GHZ}}=59\pm4\%\), \(SL=62\pm4\%\), witness \(W_{\mathrm{GHZ}}=-9\pm4\%\); order-4 Bell-product fidelity \(F=68\pm3\%\), \(SL=52\pm4\%\), with Bell-state tangles \(41\pm5\%\) and \(33\pm5\%\).
  • Process fidelities for the order-4 two-qubit gates were \(F_p=85\%,89\%\), giving product circuit fidelity \(F_p=80\%\), versus an algorithm success rate of \(99.7\%\); order-2 decomposed three-qubit gate process fidelities were \(78\%,90\%\), with only a non-useful bound \(F_p\ge20\%\).

Methods

  • Photonic linear-optics implementation with polarization-encoded qubits from parametric downconversion, using measurement-induced nonlinearity and nondeterministic gates with one-third success probability when fully prebiased; runs were flagged by fourfold coincidence events.
  • Compiled circuits for \(N=15\): the order-2 circuit was implemented directly, while the order-4 circuit was further compiled to a pair of cnot gates; the paper used quantum state and process tomography, with convex-optimization tomography and Monte-Carlo error estimation.
  • Analysis included measured density matrices, fidelities, linear entropies, entanglement witnesses/tangles, process \(\chi\)-matrices, and logical correlations between argument and function registers.

Limitations

  • The paper states that current experiments are not scalable, that compiled algorithms do not directly imply scalability, and that direct implementation of the order-4 six-photon circuit is currently infeasible due to low six-photon rates and nondeterministic gates.
  • It also states that full tomographic characterization becomes exponentially impractical for larger circuits, that order-2 process tomography would require at least 4096 measurements and was infeasible with their count rates, and that the three-qubit gate error bound is not useful.
  • Evident from the text: this is a small-scale, compiled demonstration for \(N=15\), not a full Shor implementation; the measured entangled states partially overlap with ideal states and show environmental decoherence, and the circuit fidelities are much lower than the algorithm success rates.

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

Integrity signals

Registry

Crossref · 10.1103/physrevlett.99.250505

Cites

27 of 27 references verified0 citation errors · 0 not checkable

Statistics

Nothing to recompute.

Claims the paper makes

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

  • Findingown data

    The authors measured relative nonclassical visibilities V_r of 98±2% and 85±6%.

    “We measured relative nonclassical visibilities, V r ≡V meas /V ideal , of 98±2% and 85±6%.”
    Quote in the paperSubstantial claim
  • Findingnone given

    For the first time, the authors demonstrate the core processes, coherent control, and resultant entangled states required in a full-scale implementation of Shor's algorithm.

    “For the first time we demonstrate the core processes, coherent control, and resultant entangled states that are required in a full-scale implementation of Shor's algorithm.”
    Quote in the paperSubstantial claim
  • Findingown data

    The authors implemented a compiled version of Shor's algorithm in a photonic system using single photons and measurement-induced nonlinearity.

    “Here we implement a compiled version of Shor's algorithm in a photonic system using single photons and employing the non-linearity induced by measurement.”
    • Also stated in: § Abstract · plain
      “Here we implement a compiled version of Shor's algorithm, using photonic quantum-logic gates to realise the necessary processes, and verify the resulting entanglement via quantum state and process tomography [17,18].”
    Quote in the paperSubstantial claim
  • Findingown data

    Process fidelities of F_p=85%, 89% were measured for the two-qubit gates of the order-4 circuit.

    “we measured process fidelities of F p =85%, 89% for the two-qubit gates of the order-4 circuit.”
    Quote in the paperNot a substantial claim
  • Findingown data

    The results in Fig. 5 show a clear correlation between the argument and function registers, 59 to 83% and 67 to 87% for the order-2 and order-4 circuits, respectively.

    “The results in Fig. 5 show there is a clear correlation between the argument and function registers, 59 to 83% and 67 to 87% for the order-2 and order-4 circuits, respectively.”
    Quote in the paperSubstantial claim
  • May combine two claims. 22
  • Classified as probably not a substantial claim. 7

  • May combine two claims.

    Findingown data

    In the order-4 circuit, output probabilities are 25% to within error, as expected; after classical processing half the time the algorithm finds r=4, again yielding the factors 3 and 5.

    “We measure output probabilities of 25% to within error, as expected.After classical processing half the time the algorithm finds r=4, again yielding the factors 3 and 5.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingown data

    In the order-2 circuits, the binary outputs are 00 or 10; failure and success should have equal probabilities, and the authors measure them to be 50% to within error.

    “In the order-2 circuits the binary outputs of the algorithm are 00 or 10: the former represents the expected failure mode of this circuit, the latter a successful determination of r=2; failure and success should have equal probabilities, we measure them to be 50% to within error.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingown data

    The joint state of both registers after modular exponentiation indicates circuit performance; the authors find entangled states that partially overlap with the expected states, indicating some environmental decoherence.

    “The joint state of both registers after modular exponentiation indicates circuit performance; we find entangled states that partially overlap with the expected states, Fig. 4, indicating some environmental decoherence.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingreasoning

    The order-4 circuit reduces to a pair of cnots, allowing implementation in Fig. 1g.

    “Thus the order-4 circuit, Fig. 1e), reduces to a pair of cnots, allowing us to implement the circuit in Fig. 1g).”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingown data

    The authors use a pair of compact optical gates, each operating on a dependent pair of photons, resulting in measured visibilities for both of V_r=98±2%.

    “We use a pair of compact optical gates [8,9,10], Fig 2c),e), each operating on a dependent pair of photons, resulting in measured visibilities for both of V r =98±2%.”
    Quote in the paperSubstantial claim0 of 3 sources checked
    • cites [8] source

      Not checked in the free run.

    • cites [9] source

      Not checked in the free run.

    • cites [10] source

      Not checked in the free run.

  • May combine two claims.

    Findingnone given

    The authors present two different implementations of the order-finding routine at the heart of Shor's algorithm, characterising the algorithmic and circuit performances.

    “We present two different implementations of the order-finding routine at the heart of Shor's algorithm, characterising the algorithmic and circuit performances.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingown data

    Measured fidelity with the ideal state, a tensor product of two Bell-states, is F=68±3%; the state is partially-mixed, SL=52±4%, and entangled, with tangles of the component Bell-States of 41±5% and 33±5%.

    “Measured fidelity with the ideal state, a tensor product of two Bell-states, is F =68±3%.The state is partially-mixed, SL=52±4%, and entangled, with tangles of the component Bell-States of 41±5% and 33±5%.”
    Quote in the paperSubstantial claim

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

    Interpretationcitation

    The authors use a linear-optical architecture where the required nonlinearity is induced by measurement; current experiments are not scalable, but there are clear paths to a fully scalable quantum architecture.

    “We use a linear-optical architecture where the required nonlinearity is induced by measurement; current experiments are not scalable, but there are clear paths to a fully scalable quantum architecture [19,20].”
    Quote in the paperNot a substantial claim0 of 2 sources checked
    • cites [19] source

      Not checked in the free run.

    • cites [20] source

      Not checked in the free run.

  • May combine two claims.

    Interpretationcitation

    Directly encoding the order-4 finding circuit requires six photons and at least one three-qubit and five two-qubit gates; this is currently infeasible because the best six-photon rate to date is 30 mHz, which would be reduced by six orders of magnitude using non-deterministic gates.

    “Directly encoding the order-4 finding circuit, Fig. 1e), requires six photons and at least one three-qubit and five two-qubit gates.This is currently infeasible: the best sixphoton rate to date [12] is 30 mHz, which would be reduced by six orders of magnitude using non-deterministic gates.”
    Quote in the paperSubstantial claim0 of 1 sources checked
    • cites [12] source

      Not checked in the free run.

  • May combine two claims.

    Interpretationown data

    Thus half the time the order-2 algorithm yields r=2, which gives the factors 3 and 5.

    “Thus half the time the algorithm yields r=2, which gives the factors, 3 and 5.”
    Quote in the paperSubstantial claim

  • Classified as probably not a substantial claim. May combine two claims.

    Premisecitation

    Shor's algorithm can factor a k-bit number using 72k^3 elementary quantum gates; factoring 15 requires 4608 gates operating on 21 qubits.

    “Shor's algorithm can factor a k-bit number using 72k 3 elementary quantum gates, e.g.factoring the smallest meaningful number, 15, requires 4608 gates operating on 21 qubits [13].”
    Quote in the paperSubstantial claim0 of 1 sources checked
    • cites [13] source

      Not checked in the free run.

  • May combine two claims.

    Interpretationcitation

    The fidelity of the four-qubit state with the ideal is higher than that of the three-qubit state, chiefly because the latter requires nonclassical interference of photons produced by independent sources, which suffer higher distinguishability, lowering gate performance.

    “The fidelity of the four-qubit state with the ideal, Fig. 4b), is higher than that of the three-qubit state, Fig. 4a), chiefly because the latter requires nonclassical interference of photons produced by independent sources, which suffer higher distinguishability, lowering gate performance [29,30,31].”
    Quote in the paperNot a substantial claim0 of 3 sources checked
    • cites [29]

      Not checked in the free run.

    • cites [30]

      Not checked in the free run.

    • cites [31]

      Not checked in the free run.

  • May combine two claims.

    Premisecitation

    In the liquid NMR demonstration, because the qubits are at all times in a highly mixed state and the dynamics can be fully modelled classically, neither the entanglement nor the coherent control at the core of Shor's algorithm can be implemented or verified.

    “However, since the qubits are at all times in a highly mixed state [15], and the dynamics can be fully modelled classically [16], neither the entanglement nor the coherent control at the core of Shor's algorithm can be implemented or verified.”
    Quote in the paperSubstantial claim0 of 2 sources checked
    • cites [15] source

      Not checked in the free run.

    • cites [16] source

      Not checked in the free run.

  • May combine two claims.

    Premisereasoning

    In all circuits Fig. 1b-g, the consecutive Hadamards in the top qubit of the argument-register cancel, so that this qubit and the gates controlled by it are redundant and need not be implemented experimentally.

    “For all the circuits Fig. 1b)-g), the consecutive Hadamards in the top qubit of the argument-register cancel each other out (since h 2 =i): consequently both this qubit, and the gate(s) controlled by it, are redundant and need not be implemented experimentally.”
    Quote in the paperSubstantial claim

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

    Premisecitation

    Order-finding routines are a specific case of phase-estimation routines, which in turn underpin a wide variety of quantum algorithms, such as those in quantum chemistry.

    “Order-finding routines are a specific case of phase-estimation routines, which in turn underpin a wide variety of quantum algorithms, such as those in quantum chemistry [34].”
    Quote in the paperNot a substantial claim0 of 1 sources checked
    • cites [34]

      Not checked in the free run.

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

    Interpretationcitation

    A bound can be obtained by chaining the gate errors, F_p ≥20%; this is not a useful bound, compared with the fidelity between an ideal cz and doing nothing at all of F_p=25%.

    “However, a bound can be obtained by chaining the gate errors, F p ≥20% [33].This is not a useful bound, c.f. the fidelity between an ideal cz and doing nothing at all of F p =25%!”
    Quote in the paperNot a substantial claim0 of 1 sources checked
    • cites [33]

      Not checked in the free run.

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

    Study design and conductcitation

    The authors use convex optimisation tomography to estimate errors via Monte-Carlo simulation.

    “We use convex optimisation tomography [26] to estimate errors via Monte-Carlo simulation [6].”
    Quote in the paperNot a substantial claim0 of 2 sources checked
    • cites [26] source

      Not checked in the free run.

    • cites [6] source

      Not checked in the free run.

  • May combine two claims.

    Premisereasoning

    Application of Hadamard gates in the inverse QFT resets the |k> qubits to 0, inhibiting any gates controlled by them.

    “Application of Hadamard gates in the inverse QFT reset the |k qubits to 0, inhibiting any gates controlled by them”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Premisereasoning

    The |k> qubits do not become entangled to the function-register whereas the |a> qubits are maximally-entangled to it; after tracing out the function-register, the |a> qubits are in a maximally-mixed state and any further gates acting on them are redundant.

    “The |k qubits do not become entangled to the function-register whereas the |a qubits are maximally-entangled to it-consequently after tracing out the function-register, the |a qubits are in a maximally-mixed state and any further gates acting on them are redundant.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Premisereasoning

    After modular exponentiation, for any two values x and y that differ by an integer k number of orders, C^y mod N = C^x mod N, and the state becomes a sum over k and a of |k2^l+a>|C^a mod N>.

    “After modular exponentiation, the circuit state is 2 n -1 x=0 |x |C x modN : for any two values x and y that differ by an integer, k number of orders, i.e. y-x=k 2 l , C y modN =C x modN , and the state after modular exponentiation becomes 2 n-l -1 k=0 2 l -1 a=0 |k2 l +a |C a modN .”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Premisereasoning

    The remaining argument-register qubits are maximally-entangled to the function-register; since the function-register output is not measured, these argument qubits are maximally-mixed, and the subsequent gates in the inverse QFT are therefore also redundant.

    “The remaining argumentregister qubits are maximally-entangled to the functionregister.Since the function-register output is not measured, these argument qubits are maximally-mixed, and the subsequent gates in the inverse QFT are therefore also redundant.”
    Quote in the paperSubstantial claim

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

    Interpretationnone given

    For larger circuits, full tomographic characterisation becomes exponentially impractical.

    “For larger circuits, full tomographic characterisation becomes exponentially impractical.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Premisereasoning

    The inverse QFT in Ref. [14] was unnecessary; this is true for any order-2^l circuit.

    “Thus the inverse QFT in Ref. [14] was unnecessary: indeed, it is straightforward to show this is true for any order-2 l circuit.”
    Quote in the paperNot a substantial claim0 of 1 sources checked
    • cites [14] source

      Not checked in the free run.

  • Classified as probably not a substantial claim. May combine two claims.

    Premisereasoning

    The final step of the inverse QFT is to swap the first and last qubits of the argument register, which can be done after measurement.

    “The final step of the inverse QFT is to swap the first and last qubits of the argument register which can be done after measurement.”
    Quote in the paperSubstantial claim
24 of 24

  • The authors state this as an assumption.

    Only the two-qubit gates induce error in the order-4 circuit.

    “by assuming that only these gates induce error”
1 of 1

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?

  • A compiled version of Shor's algorithm has been demonstrated using four photonic qubits by Lu et al. (2007) and Lanyon et al. (2007).

    “Recently, a compiled version of Shor's algorithm has been demonstrated using four photonic qubits by Lu et al. (2007) and Lanyon et al. (2007).”

    From Multiphoton entanglement and interferometry (2012) · cites this paper as Lanyon et al. (2007)

  • Recently there has been substantial progress in investigations of other possible candidates for AQS, such as photonic systems, photonic and polariton systems, and artificial lattices in solid state systems.

    “Recently there has also been substantial progress in investigations of other possible candidates for AQS, such as photonic systems [31, 32, 34-36], photonic and polariton systems [33, 38-42], artificial lattices in solid state systems [44].”

    From Can one trust quantum simulators? (2012) · cites this paper as [31]

Cites

Flagged first, then by citations

Research works printed but not linked: 1

  1. P. Shor, 1994, Proc. 35th Ann. Symp. Found. Comp. Sci.

Cited by

Sorted by citations

Related

Authors
Lanyon, B. P., Weinhold, T. J., Langford, N. K., Barbieri, M., James, D. F. V., Gilchrist, A., & White, A. G.
Affiliations
  • The University of Queensland (AU)
  • University of Toronto (CA)
ORCID
Venue
Physical Review Letters
Publisher
American Physical Society (APS)
Published
2007-12-19
Volume
99
Issue
25
Pages
250505-250505
ISSN
  • 0031-9007 (ISSN-L)
  • 1079-7114
DOI
10.1103/physrevlett.99.250505
OpenAlex
W1783862658
Semantic Scholar
7699daaa2beac5d1aecea718fd4c5a433e639b4a
Cited by
327
References
27
Citations by year
2026: 8 · 2025: 16 · 2024: 23 · 2023: 26 · 2022: 19 · 2021: 18 · 2020: 13 · 2019: 20 · 2018: 16 · 2017: 11 · 2016: 10 · 2015: 17 · 2014: 14 · 2013: 22 · 2012: 21
FWCI
22.88
Type
journal article
Language
en
Open access
Licence
link.aps.org/licenses/aps-default-license (vor)
Locations
  • Physical Review Letters (publishedVersion)
  • PubMed (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • Iris (Roma Tre University) (submittedVersion)
  • Griffith Research Online (submittedVersion)
  • arXiv (Cornell University)
Funders
Australian Research Council
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
Shor's algorithm, quantum factoring, photonic quantum computing, quantum entanglement, coherent control, quantum circuit compilation, scalable 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-10.

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

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