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:quant-ph/0402196 · Quantum Information and Computation

Implementation of Shor's algorithm on a linear nearest neighbour qubit array

Austin G. Fowler, Simon J. Devitt, Lloyd C. L. Hollenberg

Published Jul 1, 2004• 194 citations
arXivHTMLPDF

Abstract

Shor's algorithm, which given appropriate hardware can factorise an integer N in a time polynomial in its binary length L, has arguably spurred the race to build a practical quantum computer. Several different quantum circuits implementing Shor's algorithm have been designed, but each tacitly assumes that arbitrary pairs of qubits within the computer can be interacted. While some quantum computer architectures possess this property, many promising proposals are best suited to realising a single line of qubits with nearest neighbour interactions only. In light of this, we present a circuit implementing Shor's factorisation algorithm designed for such a linear nearest neighbour architecture. Despite the interaction restrictions, the circuit requires just 2L+4 qubits and to leading order requires 8L^4 2-qubit gates arranged in a circuit of depth 32L^3 --- identical to leading order to that possible using an architecture that can interact arbitrary pairs of qubits.

DOI
10.26421/qic4.4-1

Related papers

Investigating the practical implementation of Shor's algorithm

Simon J. Devitt, Austin G. Fowler, Lloyd C. L. Hollenberg

The publication in 1994 of Shor's algorithm, which allows factorization of composite number N in a time polynomial in its binary length L has been the primary catalyst for the race to construct a functional quantum computer. However, it seems clear that any practical system that may be developed will not be able to perform completely error free quantum gate operations or shield even idle qubits from inevitable error effects. Hence, the practicality of quantum algorithms needs to be investigated to estimate what demands must be made of quantum error correction (QEC). Several different quantum circuits implementing the quantum period finding (QPF) subroutine, which lies at the heart of Shor's algorithm have been designed, but each tacitly assumes that arbitrary pairs of qubits can be interacted. While some architectures posses this property, many promising proposals are best suited to realizing a single line of qubits with nearest neighbor interactions only. This paper will present a circuit suitable for implementing the QPF subroutine for such linear nearest neighbor (LNN) designs. We will then present direct simulation results showing for both the LNN circuit and for a circuit utilizing arbitrary interactions, that the QPF subroutine is very sensitive to a small number of errors in the entire circuit. These results can then be used to briefly examine some of the practical issues to implementing such large scale quantum algorithms.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Jan 1, 2005•0 citations

Investigating the practical implementation of Shor's algorithm

Simon J. Devitt, Austin G. Fowler, Lloyd C. L. Hollenberg

The publication in 1994 of Shor's algorithm, which allows factorization of composite number N in a time polynomial in its binary length L has been the primary catalyst for the race to construct a functional quantum computer. However, it seems clear that any practical system that may be developed will not be able to perform completely error free quantum gate operations or shield even idle qubits from inevitable error effects. Hence, the practicality of quantum algorithms needs to be investigated to estimate what demands must be made of quantum error correction (QEC). Several different quantum circuits implementing the quantum period finding (QPF) subroutine, which lies at the heart of Shor's algorithm have been designed, but each tacitly assumes that arbitrary pairs of qubits can be interacted. While some architectures posses this property, many promising proposals are best suited to realizing a single line of qubits with nearest neighbor interactions only. This paper will present a circuit suitable for implementing the QPF subroutine for such linear nearest neighbor (LNN) designs. We will then present direct simulation results showing for both the LNN circuit and for a circuit utilizing arbitrary interactions, that the QPF subroutine is very sensitive to a small number of errors in the entire circuit. These results can then be used to briefly examine some of the practical issues to implementing such large scale quantum algorithms.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Feb 23, 2005•9 citations

An Efficient Method to Convert Arbitrary Quantum Circuits to Ones on a Linear Nearest Neighbor Architecture

Yuichi Hirata, Masaki Nakanishi, Shigeru Yamashita +1 more

A variety of quantum circuits have been designed.Most of them assume that arbitrary pairs of qubits can interact.However, several promising implementations of quantum computation rely on a Linear Nearest Neighbor (LNN) architecture, which arranges quantum bits on a line, and allows neighbor interactions only.Therefore, several specific circuits have been designed on an LNN architecture.However, a general and efficient conversion technique for an arbitrary circuit has not been established.Therefore, this paper gives an efficient method that converts an arbitrary quantum circuit to one on an LNN architecture.Our method achieves small overhead and time complexity compared with naive techniques.To develop the method, we introduce two key theorems that may be interesting on their own.In addition, our method also achieves smaller overhead for some known circuits designed on an LNN architecture.

International Conference on Quantum, Nano and Micro Technologies (ICQNM)•Feb 1, 2009•73 citations

Circuit for Shor's algorithm using 2n+3 qubits

Stéphane Beauregard

We try to minimize the number of qubits needed to factor an integer of n bits using Shor's algorithm on a quantum computer. We introduce a circuit which uses 2n+3 qubits and O(n^3 lg(n)) elementary quantum gates in a depth of O(n^3) to implement the factorization algorithm. The circuit is computable in polynomial time on a classical computer and is completely general as it does not rely on any property of the number to be factored.

arXiv:quant-ph/0205095•Quantum Information and Computation•Mar 1, 2003•299 citations

The quantum Fourier transform on a linear nearest neighbor architecture

Yasuhiro Takahashi, Noboru Kunihiro, Kazuo Ohta

We show how to construct an efficient quantum circuit for computing a good approximation of the quantum Fourier transform on a linear nearest neighbor architecture. The constructed circuit uses no ancillary qubits and its depth and size are $O(n)$ and $O(n\log n)$, respectively, where $n$ is the length of the input. The circuit is useful for decreasing the size of Fowler et al.'s quantum circuit for Shor's factoring algorithm on a linear nearest neighbor architecture.

Quantum Information and Computation•May 1, 2007•36 citations

An efficient conversion of quantum circuits to a linear nearest neighbor architecture

Yuichi Hirata, Masaki Nakanishi, Shigeru Yamashita +1 more

Several promising implementations of quantum computation rely on a Linear Nearest Neighbor (LNN) architecture, which arranges quantum bits on a line, and allows neighbor interactions only. Therefore, several specific circuits have been designed on an LNN architecture. However, a general and efficient conversion method for an arbitrary circuit has not been established. Therefore, this paper gives an efficient conversion technique to convert quantum circuits to an LNN architecture. When a quantum circuit is converted to an LNN architecture, the objective is to reduce the size of the additional circuit added by the conversion and the time complexity of the conversion. The proposed method requires less additional circuitry and time complexity compared with naive techniques. To develop the method, we introduce two key theorems that may be interesting on their own. In addition, the proposed method also achieves less overhead than some known circuits designed from scratch on an LNN architecture.

Quantum Information and Computation•Jan 1, 2011•79 citations
Shor's algorithm, which given appropriate hardware can factorise an integer N in a time polynomial in its binary length L, has arguably spurred the race to build a practical quantum computer. Several different quantum circuits implementing Shor's algorithm have been designed, but each tacitly assumes that arbitrary pairs of qubits within the computer can be interacted. While some quantum computer architectures possess this property, many promising proposals are best suited to realising a single line of qubits with nearest neighbour interactions only. In light of this, we present a circuit implementing Shor's factorisation algorithm designed for such a linear nearest neighbour architecture. Despite the interaction restrictions, the circuit requires just 2L+4 qubits and to leading order requires 8L^4 2-qubit gates arranged in a circuit of depth 32L^3 --- identical to leading order to that possible using an architecture that can interact arbitrary pairs of qubits.
The publication in 1994 of Shor's algorithm, which allows factorization of composite number N in a time polynomial in its binary length L has been the primary catalyst for the race to construct a functional quantum computer. However, it seems clear that any practical system that may be developed will not be able to perform completely error free quantum gate operations or shield even idle qubits from inevitable error effects. Hence, the practicality of quantum algorithms needs to be investigated to estimate what demands must be made of quantum error correction (QEC). Several different quantum circuits implementing the quantum period finding (QPF) subroutine, which lies at the heart of Shor's algorithm have been designed, but each tacitly assumes that arbitrary pairs of qubits can be interacted. While some architectures posses this property, many promising proposals are best suited to realizing a single line of qubits with nearest neighbor interactions only. This paper will present a circuit suitable for implementing the QPF subroutine for such linear nearest neighbor (LNN) designs. We will then present direct simulation results showing for both the LNN circuit and for a circuit utilizing arbitrary interactions, that the QPF subroutine is very sensitive to a small number of errors in the entire circuit. These results can then be used to briefly examine some of the practical issues to implementing such large scale quantum algorithms.
The publication in 1994 of Shor's algorithm, which allows factorization of composite number N in a time polynomial in its binary length L has been the primary catalyst for the race to construct a functional quantum computer. However, it seems clear that any practical system that may be developed will not be able to perform completely error free quantum gate operations or shield even idle qubits from inevitable error effects. Hence, the practicality of quantum algorithms needs to be investigated to estimate what demands must be made of quantum error correction (QEC). Several different quantum circuits implementing the quantum period finding (QPF) subroutine, which lies at the heart of Shor's algorithm have been designed, but each tacitly assumes that arbitrary pairs of qubits can be interacted. While some architectures posses this property, many promising proposals are best suited to realizing a single line of qubits with nearest neighbor interactions only. This paper will present a circuit suitable for implementing the QPF subroutine for such linear nearest neighbor (LNN) designs. We will then present direct simulation results showing for both the LNN circuit and for a circuit utilizing arbitrary interactions, that the QPF subroutine is very sensitive to a small number of errors in the entire circuit. These results can then be used to briefly examine some of the practical issues to implementing such large scale quantum algorithms.
A variety of quantum circuits have been designed.Most of them assume that arbitrary pairs of qubits can interact.However, several promising implementations of quantum computation rely on a Linear Nearest Neighbor (LNN) architecture, which arranges quantum bits on a line, and allows neighbor interactions only.Therefore, several specific circuits have been designed on an LNN architecture.However, a general and efficient conversion technique for an arbitrary circuit has not been established.Therefore, this paper gives an efficient method that converts an arbitrary quantum circuit to one on an LNN architecture.Our method achieves small overhead and time complexity compared with naive techniques.To develop the method, we introduce two key theorems that may be interesting on their own.In addition, our method also achieves smaller overhead for some known circuits designed on an LNN architecture.
We show how to construct an efficient quantum circuit for computing a good approximation of the quantum Fourier transform on a linear nearest neighbor architecture. The constructed circuit uses no ancillary qubits and its depth and size are O(n)O(n)O(n) and O(nlog⁡n)O(n\log n)O(nlogn), respectively, where nnn is the length of the input. The circuit is useful for decreasing the size of Fowler et al.'s quantum circuit for Shor's factoring algorithm on a linear nearest neighbor architecture.
Several promising implementations of quantum computation rely on a Linear Nearest Neighbor (LNN) architecture, which arranges quantum bits on a line, and allows neighbor interactions only. Therefore, several specific circuits have been designed on an LNN architecture. However, a general and efficient conversion method for an arbitrary circuit has not been established. Therefore, this paper gives an efficient conversion technique to convert quantum circuits to an LNN architecture. When a quantum circuit is converted to an LNN architecture, the objective is to reduce the size of the additional circuit added by the conversion and the time complexity of the conversion. The proposed method requires less additional circuitry and time complexity compared with naive techniques. To develop the method, we introduce two key theorems that may be interesting on their own. In addition, the proposed method also achieves less overhead than some known circuits designed from scratch on an LNN architecture.