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/9505011 · Physical Review A

Simple quantum computer

Isaac L. Chuang, Y. Yamamoto

Published Nov 1, 1995• 455 citations
arXivHTMLPDF

Abstract

We propose an implementation of a quantum computer to solve Deutsch's problem, which requires exponential time on a classical computer but only linear time with quantum parallelism. By using a dual-rail quantum-bit representation as a simple form of error correction, our machine can tolerate some amount of decoherence and still give the correct result with high probability. The design that we employ also demonstrates a signature for quantum parallelism which unambiguously distinguishes the desired quantum behavior from the merely classical. The experimental demonstration of our proposal using quantum optical components calls for the development of several key technologies common to single photonics.

DOI
10.1103/physreva.52.3489

Related papers

Quantum computation using linear optics

Gerard J Milburn

Summary form only given. Quantum computers are expected to increase the efficiency of solving problems such as factoring large integers. However an experimental implementation of even relatively simple quantum information processing with a few to a dozen qubits presents an enormous technological challenge. One of the earliest proposals for quantum computation is based on implementing a quantum bit with two optical modes containing one photon. The proposal is appealing due to the ease with which photon interference can be observed. However these early proposals required huge single photon optical nonlinearities. Unfortunately currently available optical nonlinearities are too weak and too noisy to be useful. Recently however we have discovered that efficient quantum computation is possible using only beam splitters, phase shifters, single photon sources and photodetectors. Our methods exploit feed forward from photo-detectors and are robust against errors from photon loss and detector inefficiency. In this tutorial I will outline this scheme, highlighting the technical challenges required to implement it. The tutorial will be relatively self contained with a brief introduction to quantum optics and quantum computation.

Quantum Electronics and Laser Science Conference•Jun 25, 2003•0 citations

Experimental demonstration of a three-qubit quantum computation algorithm using a single photon and linear optics

Shigeki Takeuchi

A quantum computer that gives us the result of a single quantum computation has been constructed. The quantum register was realized by modes and polarization of photons, and the unitary transformation was implemented with linear optics. For each quantum computation, the answer to the Deutsch Jozsa problem for any four-bit digit is given by a single-photon detection signal with a small error rate of less than 4%.

Physical Review A•Aug 3, 2000•51 citations

A simple quantum computer: Experimental realization of quantum computation algorithms with linear optics

Shigeki Takeuchi

Abstract In efforts toward the realization of quantum computers, there have been many proposals to implement controlled NOT gates between quantum bits (qubits). However, the number of quanta in the experimentally realized system has been at most two. Because it is difficult to cope with both the realization of the conditional interaction (e.g., huge nonlinear interaction) between the quanta, and the maintenance of quantum coherence for a sufficient time, the realization of quantum logic gates using several quanta may be difficult in the near future. In this paper, a new method which implements a quantum algorithm using linear optics and single photons is described. This method does not need any huge nonlinearity. Hence, it is practical with today's technology and will be one of the useful physical test beds for the quantum algorithms. The optical implementation of the Deutsch–Jozsa algorithm with a 4‐bit input is proposed, and the mechanism is explained. As one instance of the recent progress of our project, an experiment of single‐photon interference using parametric fluorescence with highly stabilized interferometer system is reported. © 2001 Scripta Technica, Electron Comm Jpn Pt 3, 84(11): 52–60, 2001

Electronics and Communications in Japan (Part III Fundamental Electronic Science)•May 23, 2001•5 citations

The Study on Structure and Character of Photon Quantum Computer

Jun Lu

The photon is an attractive physical system for representing a quantum bit. Single photons can be detected with high quantum efficiency for a wide range of wavelengths, using a variety of technologies. Three of the most experimentally accessible devices for manipulating photon states are mirrors, phase shifters and beam splitters. Arbitrary unitary transforms can be applied to quantum information, encoded with single photons in the dual-rail representation, using phase shifters and beam splitters. We have gained some valuable insight into the nature of the architecture and system design of a quantum computer, from studying this optical quantum computer.

ASME Press eBooks•Jan 1, 2012•0 citations

Overflow-Safe Polylog-Time Parallel Minimum-Weight Perfect Matching Decoder: Toward Experimental Demonstration

Ryo Mikami, Hayata Yamasaki

Fault-tolerant quantum computation (FTQC) requires fast and accurate decoding of quantum errors, which is often formulated as a minimum-weight perfect matching (MWPM) problem. A determinant-based approach has been proposed as a novel method to surpass the conventional polynomial runtime of MWPM decoding via the blossom algorithm, asymptotically achieving polylogarithmic parallel runtime. However, the existing approach requires an impractically large bit length to represent intermediate values during the computation of the matrix determinant; moreover, when implemented on a finite-bit machine, the algorithm cannot detect overflow, and therefore, the mathematical correctness of such algorithms cannot be guaranteed. In this work, we address these issues by presenting a polylog-time MWPM decoder that detects overflow in finite-bit representations by employing an algebraic framework over a truncated polynomial ring. Within this framework, all arithmetic operations are implemented using bitwise XOR and shift operations, enabling efficient and hardware-friendly implementation. Furthermore, with algorithmic optimizations tailored to the structure of the determinant-based approach, we reduce the arithmetic bit length required to represent intermediate values in the determinant computation by more than $99.9\%$, making it possible to implement it on machines supporting $512$-bit computing while preserving the decoder's polylog runtime scaling. These results open the possibility of a proof-of-principle demonstration of the polylog-time MWPM decoding in the early FTQC regime.

quant-pharXiv:2603.03776•Physical Review A•Mar 5, 2026•1 citation

Cavity QED Deutsch quantum computer

Lloyd C. L. Hollenberg, A. N. Salgueiro, Maria Carolina Nemes

The two-atom correlation scheme originally proposed by Davidovich, Brune, Raimond, and Haroche for measuring the decoherence of a mesoscopic superposition of coherent states of a QED cavity field is shown to be equivalent to a quantum computer solving Deutsch's problem. Using the existing analysis of decoherence in the Master equation formalism, and other important losses in this system, the final probability for obtaining the correct result for the computation is found in terms of the time period between atom traversals, the number of photons in the cavity, and the precision of the atomic velocity. The error due to decoherence in this system amounts to a phase error, and in the Master equation approach is a linear effect at small time scales. By explicitly considering the dynamics of the decoherence process when the system is coupled to a bath of oscillators with finite mode cutoff the error due to decoherence is found to decrease significantly and becomes a quadratic effect at short-time scales.

Physical Review A•Sep 13, 2001•5 citations
We propose an implementation of a quantum computer to solve Deutsch's problem, which requires exponential time on a classical computer but only linear time with quantum parallelism. By using a dual-rail quantum-bit representation as a simple form of error correction, our machine can tolerate some amount of decoherence and still give the correct result with high probability. The design that we employ also demonstrates a signature for quantum parallelism which unambiguously distinguishes the desired quantum behavior from the merely classical. The experimental demonstration of our proposal using quantum optical components calls for the development of several key technologies common to single photonics.
Summary form only given. Quantum computers are expected to increase the efficiency of solving problems such as factoring large integers. However an experimental implementation of even relatively simple quantum information processing with a few to a dozen qubits presents an enormous technological challenge. One of the earliest proposals for quantum computation is based on implementing a quantum bit with two optical modes containing one photon. The proposal is appealing due to the ease with which photon interference can be observed. However these early proposals required huge single photon optical nonlinearities. Unfortunately currently available optical nonlinearities are too weak and too noisy to be useful. Recently however we have discovered that efficient quantum computation is possible using only beam splitters, phase shifters, single photon sources and photodetectors. Our methods exploit feed forward from photo-detectors and are robust against errors from photon loss and detector inefficiency. In this tutorial I will outline this scheme, highlighting the technical challenges required to implement it. The tutorial will be relatively self contained with a brief introduction to quantum optics and quantum computation.
Abstract In efforts toward the realization of quantum computers, there have been many proposals to implement controlled NOT gates between quantum bits (qubits). However, the number of quanta in the experimentally realized system has been at most two. Because it is difficult to cope with both the realization of the conditional interaction (e.g., huge nonlinear interaction) between the quanta, and the maintenance of quantum coherence for a sufficient time, the realization of quantum logic gates using several quanta may be difficult in the near future. In this paper, a new method which implements a quantum algorithm using linear optics and single photons is described. This method does not need any huge nonlinearity. Hence, it is practical with today's technology and will be one of the useful physical test beds for the quantum algorithms. The optical implementation of the Deutsch–Jozsa algorithm with a 4‐bit input is proposed, and the mechanism is explained. As one instance of the recent progress of our project, an experiment of single‐photon interference using parametric fluorescence with highly stabilized interferometer system is reported. © 2001 Scripta Technica, Electron Comm Jpn Pt 3, 84(11): 52–60, 2001
The photon is an attractive physical system for representing a quantum bit. Single photons can be detected with high quantum efficiency for a wide range of wavelengths, using a variety of technologies. Three of the most experimentally accessible devices for manipulating photon states are mirrors, phase shifters and beam splitters. Arbitrary unitary transforms can be applied to quantum information, encoded with single photons in the dual-rail representation, using phase shifters and beam splitters. We have gained some valuable insight into the nature of the architecture and system design of a quantum computer, from studying this optical quantum computer.
Fault-tolerant quantum computation (FTQC) requires fast and accurate decoding of quantum errors, which is often formulated as a minimum-weight perfect matching (MWPM) problem. A determinant-based approach has been proposed as a novel method to surpass the conventional polynomial runtime of MWPM decoding via the blossom algorithm, asymptotically achieving polylogarithmic parallel runtime. However, the existing approach requires an impractically large bit length to represent intermediate values during the computation of the matrix determinant; moreover, when implemented on a finite-bit machine, the algorithm cannot detect overflow, and therefore, the mathematical correctness of such algorithms cannot be guaranteed. In this work, we address these issues by presenting a polylog-time MWPM decoder that detects overflow in finite-bit representations by employing an algebraic framework over a truncated polynomial ring. Within this framework, all arithmetic operations are implemented using bitwise XOR and shift operations, enabling efficient and hardware-friendly implementation. Furthermore, with algorithmic optimizations tailored to the structure of the determinant-based approach, we reduce the arithmetic bit length required to represent intermediate values in the determinant computation by more than 99.9%99.9\%99.9%, making it possible to implement it on machines supporting 512512512-bit computing while preserving the decoder's polylog runtime scaling. These results open the possibility of a proof-of-principle demonstration of the polylog-time MWPM decoding in the early FTQC regime.
The two-atom correlation scheme originally proposed by Davidovich, Brune, Raimond, and Haroche for measuring the decoherence of a mesoscopic superposition of coherent states of a QED cavity field is shown to be equivalent to a quantum computer solving Deutsch's problem. Using the existing analysis of decoherence in the Master equation formalism, and other important losses in this system, the final probability for obtaining the correct result for the computation is found in terms of the time period between atom traversals, the number of photons in the cavity, and the precision of the atomic velocity. The error due to decoherence in this system amounts to a phase error, and in the Master equation approach is a linear effect at small time scales. By explicitly considering the dynamics of the decoherence process when the system is coupled to a bath of oscillators with finite mode cutoff the error due to decoherence is found to decrease significantly and becomes a quadratic effect at short-time scales.