Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:0705.1684 · Physical Review Letters

Demonstration of a Compiled Version of Shor’s Quantum Factoring Algorithm Using Photonic Qubits

Chao‐Yang Lu, Dan E. Browne, Tao Yang, Jian-Wei Pan

Published Dec 19, 2007• 288 citations
arXivHTMLPDF

Abstract

We report an experimental demonstration of a complied version of Shor's algorithm using four photonic qubits. We choose the simplest instance of this algorithm, that is, factorization of N=15 in the case that the period r=2 and exploit a simplified linear optical network to coherently implement the quantum circuits of the modular exponential execution and semiclassical quantum Fourier transformation. During this computation, genuine multiparticle entanglement is observed which well supports its quantum nature. This experiment represents an essential step toward full realization of Shor's algorithm and scalable linear optics quantum computation.

DOI
10.1103/physrevlett.99.250504

Related papers

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

B. P. Lanyon, Till J. Weinhold, Nathan K. Langford +4 more

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.

arXiv:0705.1398•Physical Review Letters•Dec 19, 2007•345 citations

Proof-of-principle demonstration of compiled Shor’s algorithm using a quantum dot single-photon source

Z.-C. Duan, Jin-Peng Li, Jian Qin +7 more

We report a proof-of-principle demonstration of Shor's algorithm with photons generated by an on-demand semiconductor quantum dot single-photon source for the first time. A fully compiled version of Shor's algorithm for factoring 15 has been accomplished with a significantly reduced resource requirement that employs the four-photon cluster state. Genuine multiparticle entanglement properties are confirmed to reveal the quantum character of the algorithm and circuit. The implementation realizes the Shor's algorithm with deterministic photonic qubits, which opens new applications for cluster state beyond one-way quantum computing.

Optics Express•Jun 4, 2020•27 citations

Experimental realisation of Shor's quantum factoring algorithm using qubit recycling

Enrique Martín-López, Anthony Laing, Thomas Lawson +3 more

Quantum algorithms are computational routines that exploit quantum mechanics to solve problems exponentially faster than the best classical algorithms. Shor's quantum factoring algorithm is a key example and the prime motivator in the international effort to realise a quantum computer. However, due to the large number of resources required, to date, there have been only four small scale demonstrations. Here we address this resource demand and demonstrate a scalable version of Shor's algorithm in which then qubit control register is replaced by a single qubit that is recycled n times: the total number of qubits is one third of that required in the standard protocol. Encoding the work register in higher-dimensional states, we implement a two-photon compiled algorithm to factor N = 21. Significantly, the algorithmic output exhibits structure that is distinguishable from noise, in contrast to previous demonstrations.

Conference on Lasers and Electro-Optics Europe & European Quantum Electronics Conference (CLEO/Europe-EQEC)•May 1, 2013•8 citations

Shor’s Quantum Factoring Algorithm on a Photonic Chip

Alberto Politi, Jonathan C. F. Matthews, Jeremy L. O’Brien

Shor's quantum factoring algorithm finds the prime factors of a large number exponentially faster than any other known method, a task that lies at the heart of modern information security, particularly on the Internet. This algorithm requires a quantum computer, a device that harnesses the massive parallelism afforded by quantum superposition and entanglement of quantum bits (or qubits). We report the demonstration of a compiled version of Shor's algorithm on an integrated waveguide silica-on-silicon chip that guides four single-photon qubits through the computation to factor 15.

arXiv:0911.1242•Science•Sep 3, 2009•491 citations

Shor’s quantum algorithm using electrons in semiconductor nanostructures

Fabrizio Buscemi

Shor's factoring algorithm illustrates the potential power of quantum computation. Here, we present and numerically investigate a proposal for a compiled version of such an algorithm based on a quantum-wire network by exploiting the potential of fully coherent electron transport assisted by the surface acoustic waves. Specifically, a nonstandard approach is used to implement, in a simple form, the quantum circuits of the modular exponentiation execution for the simplest instance of Shor's algorithm, that is, the factorization of $N=15$. The numerical procedure is based on a time-dependent solution of the multiparticle Schr\"odinger equation. The near-ideal algorithm performance and the large estimated fidelity indicate the efficiency of the protocol implemented, which also is almost insensitive to small destabilizing effects during quantum computation.

arXiv:1011.2628•Physical Review A•Jan 12, 2011•16 citations

Circuit implementation of Shor's algorithm for the factorization of small integers in Qiskit

Iheb Eddine Gharbi, Amor Gueddana, Hichem Eleuch +1 more

To factor an integer N into a product of two other numbers N1 and N2, Shor’s algorithm uses the Quantum Fourier Transform on n qubits, denoted QFTn, to determine the period r of a Modular Exponentiation Function (MEF), which is later used to compute a factor of N. In this work, we present Shor’s algorithm for factoring an integer of n qubits and illustrate an example with n=4. We implement our algorithm using Qiskit and IBM quantum computers, which also can be adapted on other quantum computing platforms with minor adjustments. We discuss the IBM quantum computer limitations for running our circuit and show the impact of device imperfections on the factored result.

Quantum Communications and Quantum Imaging•Aug 13, 2024•3 citations
We report an experimental demonstration of a complied version of Shor's algorithm using four photonic qubits. We choose the simplest instance of this algorithm, that is, factorization of N=15 in the case that the period r=2 and exploit a simplified linear optical network to coherently implement the quantum circuits of the modular exponential execution and semiclassical quantum Fourier transformation. During this computation, genuine multiparticle entanglement is observed which well supports its quantum nature. This experiment represents an essential step toward full realization of Shor's algorithm and scalable linear optics quantum computation.
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.
We report a proof-of-principle demonstration of Shor's algorithm with photons generated by an on-demand semiconductor quantum dot single-photon source for the first time. A fully compiled version of Shor's algorithm for factoring 15 has been accomplished with a significantly reduced resource requirement that employs the four-photon cluster state. Genuine multiparticle entanglement properties are confirmed to reveal the quantum character of the algorithm and circuit. The implementation realizes the Shor's algorithm with deterministic photonic qubits, which opens new applications for cluster state beyond one-way quantum computing.
Quantum algorithms are computational routines that exploit quantum mechanics to solve problems exponentially faster than the best classical algorithms. Shor's quantum factoring algorithm is a key example and the prime motivator in the international effort to realise a quantum computer. However, due to the large number of resources required, to date, there have been only four small scale demonstrations. Here we address this resource demand and demonstrate a scalable version of Shor's algorithm in which then qubit control register is replaced by a single qubit that is recycled n times: the total number of qubits is one third of that required in the standard protocol. Encoding the work register in higher-dimensional states, we implement a two-photon compiled algorithm to factor N = 21. Significantly, the algorithmic output exhibits structure that is distinguishable from noise, in contrast to previous demonstrations.
Shor's quantum factoring algorithm finds the prime factors of a large number exponentially faster than any other known method, a task that lies at the heart of modern information security, particularly on the Internet. This algorithm requires a quantum computer, a device that harnesses the massive parallelism afforded by quantum superposition and entanglement of quantum bits (or qubits). We report the demonstration of a compiled version of Shor's algorithm on an integrated waveguide silica-on-silicon chip that guides four single-photon qubits through the computation to factor 15.
Shor's factoring algorithm illustrates the potential power of quantum computation. Here, we present and numerically investigate a proposal for a compiled version of such an algorithm based on a quantum-wire network by exploiting the potential of fully coherent electron transport assisted by the surface acoustic waves. Specifically, a nonstandard approach is used to implement, in a simple form, the quantum circuits of the modular exponentiation execution for the simplest instance of Shor's algorithm, that is, the factorization of N=15N=15N=15. The numerical procedure is based on a time-dependent solution of the multiparticle Schr\"odinger equation. The near-ideal algorithm performance and the large estimated fidelity indicate the efficiency of the protocol implemented, which also is almost insensitive to small destabilizing effects during quantum computation.
To factor an integer N into a product of two other numbers N1 and N2, Shor’s algorithm uses the Quantum Fourier Transform on n qubits, denoted QFTn, to determine the period r of a Modular Exponentiation Function (MEF), which is later used to compute a factor of N. In this work, we present Shor’s algorithm for factoring an integer of n qubits and illustrate an example with n=4. We implement our algorithm using Qiskit and IBM quantum computers, which also can be adapted on other quantum computing platforms with minor adjustments. We discuss the IBM quantum computer limitations for running our circuit and show the impact of device imperfections on the factored result.