CoChat
Sign Up
PreprintCited by 1,390Quantum Information and CryptographyQuantum Computing Algorithms and ArchitectureQuantum Mechanics and Applications

Quantum Computing

Open access
Steane, Andrew·1997·arXiv
DOI 10.48550/arxiv.quant-ph/9708022arXiv quant-ph/9708022
Open this paper in CoChat — free accountOpen PDF

Abstract

The subject of quantum computing brings together ideas from classical information theory, computer science, and quantum physics. This review aims to summarise not just quantum computing, but the whole subject of quantum information theory. It turns out that information theory and quantum mechanics fit together very well. In order to explain their relationship, the review begins with an introduction to classical information theory and computer science, including Shannon's theorem, error correcting codes, Turing machines and computational complexity. The principles of quantum mechanics are then outlined, and the EPR experiment described. The EPR-Bell correlations, and quantum entanglement in general, form the essential new ingredient which distinguishes quantum from classical information theory, and, arguably, quantum from classical physics. Basic quantum information ideas are described, including key distribution, teleportation, data compression, quantum error correction, the universal quantum computer and quantum algorithms. The common theme of all these ideas is the use of quantum entanglement as a computational resource. Experimental methods for small quantum processors are briefly sketched, concentrating on ion traps, high Q cavities, and NMR. The review concludes with an outline of the main features of quantum information physics, and avenues for future research.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.quant-ph/9708022

Cites

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

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?

  • An efficient quantum computation should, for some initial states, have a final state that is reasonably distinct from its initial state.

    “At the least, an efficient quantum computation should, for some initial states, have a final state that is reasonably distinct from its initial state.”

    From The maximum speed of dynamical evolution (1998) · cites this paper as [19]

    Section 7.2 (page unavailable) describes an efficient period-finding computation whose registers begin in |0⟩ and whose final x-register state yields a measured result that can differ from the initial value. That supports the possibility of a distinct final state, but the paper does not state the claim’s general expectation for efficient quantum computations. (LLM, conf=0.75)

    Experimental — accuracy not yet measured

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

No references could be resolved yet.

Research works printed but not linked: 50

  1. Aharonov D and Ben-Or M 1996 Fault-tolerant quantum computation with constant error Preprint quant- ph/9611025 Aspect A 1991 Testing Bell's inequalities Europhys. News 22 73-5
  2. Barenco A 1995 A universal two-bit gate for quantum computation Proc. R. Soc. A 449 679-83 --1996 Quantum physics and computers Contemp. Phys. 37 375-89
  3. --1966 On the problem of hidden variables in quantum theory Rev. Mod. Phys. 38 447-52 --1987 Speakable and Unspeakable in Quantum Mechanics (Cambridge: Cambridge University Press)
  4. Bennett C H, Bernstein E, Brassard G and Vazirani U 1997 Strengths and weaknesses of quantum computing Preprint quant-ph/9701001 · arXiv
  5. Bennett C H and Brassard G 1984 Quantum cryptography: public key distribution and coin tossing Proc. IEEE Conf. on Computers, Syst. and Signal Process. pp 175-9 --1989 SIGACT News 20 78-82
  6. Bennett C H, Brassard G, Briedbart S and Wiesner S 1982 Quantum cryptography, or unforgeable subway tokens Advances in Cryptology: Proceedings of Crypto '82 (New York: Plenum) pp 267-75
  7. Bernstein E and Vazirani U 1993 Quantum complexity theory Proc. 25th Annual ACM Symposium on Theory of Computing (New York: ACM) pp 11-20
  8. Berthiaume A and Brassard G 1992a The quantum challenge to structural complexity theory Proc. 7th Annual Structure in Complexity Theory Conf. (Los Alamitos, CA: IEEE Computer Society Press) pp 132-7 --1992b Oracle quantum computing Proc. Workshop on Physics of Computation: PhysComp '92 (Los Alamitos, CA: IEEE Computer Society Press) pp 60-2
  9. Berthiaume A, Deutsch D and Jozsa R 1994 The stabilisation of quantum computation Proc. Workshop on Physics and Computation, PhysComp 94 pp 60-2 (Los Alamitos, CA: IEEE Computer Society Press)
  10. Boghosian B M and Taylor W 1997 Simulating quantum mechanics on a quantum computer Preprint quant- ph/9701019
  11. Boyer M, Brassard G, Hoyer P and Tapp A 1996 Tight bounds on quantum searching Preprint quant-ph/9605034 · arXiv
  12. Calderbank A R, Rains E M, Shor P W and Sloane N J A 1996 Quantum error correction via codes over GF (4) IEEE Trans. Inf. Theor. to be published --1997 Quantum error correction and orthogonal geometry Phys. Rev. Lett. 78 405-8
  13. Cory D G, Fahmy A F and Havel T F 1996 Nuclear magnetic resonance spectroscopy: an experimentally accessible paradigm for quantum computing Proc. 4th Workshop on Physics and Computation (Boston, MA: Complex Systems Institute)
  14. Deutsch D 1985 Quantum theory, the Church-Turing principle and the universal quantum computer Proc. R. Soc. A 400 97-117
  15. --1989 Quantum computational networks Proc. R. Soc. A 425 73-90
  16. Deutsch D, Barenco A and Ekert A 1995 Universality in quantum computation Proc. R. Soc. A 449 669-77
  17. Deutsch D and Jozsa R 1992 Rapid solution of problems by quantum computation Proc. R. Soc. A 439 553-8
  18. Ekert A 1991 Quantum cryptography based on Bell's theorem Phys. Rev. Lett. 67 661-3 --1997 From quantum code-making to quantum code-breaking Preprint quant-ph/9703035 · arXiv
  19. Glauber R J 1986 Frontiers in Quantum Optics ed E R Pike and S Sarker (Bristol: Hilger) Golay M J E 1949 Notes on digital coding Proc. IEEE 37 657
  20. Gottesman D 1996 Class of quantum error-correcting codes saturating the quantum Hamming bound Phys. Rev. A 54 1862-8 --1997 A theory of fault-tolerant quantum computation Preprint quant-ph 9702029
  21. Hardy G H and Wright E M 1979 An Introduction to the Theory of Numbers (Oxford: Clarendon)
  22. Hill R 1986 A First Course in Coding Theory (Oxford: Clarendon)
  23. Jones D S 1979 Elementary Information Theory (Oxford: Clarendon)
  24. Jozsa R 1997a Entanglement and quantum computation Geometric Issues in the Foundations of Science ed S Huggett et al (Oxford: Oxford University Press) --1997b Quantum algorithms and the Fourier transform Proc. Santa Barbara Conf. on Quantum Coherence and Decoherence Preprint quant-ph/9707033, submitted · arXiv
  25. Kitaev A Yu 1995 Quantum measurements and the Abelian stablizer problem Preprint quant-ph/9511026 · arXiv
  26. --1996 Quantum error correction with imperfect gates Preprint --1997 Fault-tolerant quantum computation by anyons Preprint quant-ph/9707021 · arXiv
  27. Knill E and Laflamme R 1996 Concatenated quantum codes Preprint quant-ph/9608012 · arXiv
  28. Knill E, Laflamme R and Zurek W H 1996 Accuracy threshold for quantum computation Preprint quant-ph/9610011 · arXiv
  29. --1997 Resilient quantum computation: error models and thresholds Preprint quant-ph/9702058 · arXiv
  30. Knuth D E 1981 Seminumerical Algorithms (The Art of Computer Programming 2), 2nd edn (Reading, MA: Addison-Wesley).
  31. Landauer R 1961 IBM J. Res. Dev. 5 183 --1991 Information is physical Phys. Today May 23-9 --1995 Is quantum mechanics useful? Phil. Trans. R. Soc. A 353 367-76 --1996 The physical nature of information Phys. Lett. A 217 188
  32. Levitin L B 1987 Information Complexity and Control in Quantum Physics ed A Blaquieve, S Diner and G Lochak (New York: Springer) pp 15-47
  33. Loss D and DiVincenzo D P 1997 Quantum computation with quantum dots Phys. Rev. A submitted MacWilliams F J and Sloane N J A 1977 The Theory of Error Correcting Codes (Amsterdam: Elsevier)
  34. --1990 Parallel quantum computation Complexity, Entropy and the Physics of Information (Santa Fe Institute Studies in the Sciences of Complexity VIII) ed W H Zurek (Reading, MA: Addison-Wesley) p 273
  35. Palma G M, Suominen K-A and Ekert A K 1996 Quantum computers and dissipation Proc. R. Soc. A 452 567-84
  36. Preskill J 1997 Reliable quantum computers Preprint quant-ph/9705031 · arXiv
  37. Privman V, Vagner I D and Kventsel G 1997 Quantum computation in quantum-Hall systems Preprint quant- ph/9707017
  38. Schroeder M R 1984 Number Theory in Science and Communication (Berlin: Springer)
  39. Shor P W 1994 Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer Proc. 35th Annual Symp. on Foundations of Computer Science (Santa Fe, NM: IEEE Computer Society Press) (revised version 1995a Preprint quant-ph/9508027) · arXiv
  40. --1995b Scheme for reducing decoherence in quantum computer memory Phys. Rev. A 52 R2493-6 --1996 Fault tolerant quantum computation Proc. 37th Annual Symp. on Foundations of Computer Science (Los Alamitos, CA: IEEE Computer Society Press) pp 56-65
  41. Simon D 1994 On the power of quantum computation Proc. 35th Annual Symp. on Foundations of Computer Science (Los Alamitos, CA: IEEE Computer Society Press) pp 124-34
  42. Slepian D (ed) 1974 Key Papers in the Development of Information Theory (New York: IEEE) Special issue: Quantum communication 1994 J. Mod. Opt. 41
  43. Spiller T P 1996 Quantum information processing: cryptography, computation and teleportation Proc. IEEE 84 1719-46
  44. Steane A M 1996a Error correcting codes in quantum theory Phys. Rev. Lett. 77 793-7 --1996b Multiple particle interference and quantum error correction Proc. R. Soc. A 452 2551-77 --1996c Simple quantum error-correcting codes Phys. Rev. A 54 4741-51 --1996d Quantum Reed-Muller codes IEEE Trans. Inf. Theor. to be published --1997a Active stabilisation, quantum computation, and quantum state sythesis Phys. Rev. Lett. 78 2252-5 --1997b The ion trap quantum information processor Appl. Phys. B 64 623-42
  45. --1997c Space, time, parallelism and noise requirements for reliable quantum computing Preprint quant- ph/9708021
  46. Toffoli T 1980 Reversible computing Automata, Languages and Programming, 7th Colloquium (Lecture Notes in Computer Science 84) ed J W de Bakker and J van Leeuwen (Berlin: Springer) pp 632-44
  47. Turing A M 1936 On computable numbers, with an application to the Entschneidungsproblem Proc. Lond. Math. Soc. Ser. 42 230 (see also Proc. Lond. Math. Soc. Ser. 43 544)
  48. Wheeler J A and Zurek W H (ed) 1983 Quantum Theory and Measurement (Princeton, NJ: Princeton University Press)
  49. Wiesner S 1983 Conjugate coding SIGACT News 15 78-88 --1996 Simulations of many-body quantum systems by a quantum computer Preprint quant-ph/9603028 · arXiv
  50. Zalka C 1996 Efficient simulation of quantum systems by quantum computers Preprint quant-ph/9603026 · arXiv

Cited by

Sorted by citations

Authors
Steane, A.
Affiliations
University of Oxford (GB)
Corresponding author
Steane, Andrew
ORCID
Steane, Andrew
Venue
arXiv
Publisher
arXiv
Published
1997
Volume
61
Issue
2
Pages
117-173
ISSN
0034-4885 (ISSN-L)
DOI
10.48550/arxiv.quant-ph/9708022
arXiv
quant-ph/9708022
OpenAlex
W3037315640
Cited by
1,390
References
0
Citations by year
2026: 66 · 2025: 126 · 2024: 97 · 2023: 90 · 2022: 75 · 2021: 59 · 2020: 39 · 2019: 36 · 2018: 33 · 2017: 25 · 2016: 16 · 2015: 18 · 2014: 15 · 2013: 26 · 2012: 25
FWCI
111.34
Type
journal article
Language
en
Open access
Licence
arxiv.org/licenses/assumed-1991-2003/
Locations
  • Reports on Progress in Physics (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Topics
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Information and Cryptography
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Mechanics and Applications
Keywords
quantum computing, quantum information, quantum entanglement, quantum cryptography, quantum teleportation, quantum error correction, qubits, no-cloning theorem, quantum gates, quantum algorithms, Shor's algorithm, Grover's algorithm, computational complexity, linear ion trap, optical resonators, nuclear magnetic resonance

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.

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