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

WORLD SCIENTIFIC eBooks

QUANTUM COMPUTATION: AN INTRODUCTION

Adriano Barenco

Published Oct 1, 1998• 13 citations
Publisher

Abstract

When applied to computation, quantum mechanics opens completely new perspectives; by exploiting quantum mechanical features such as entanglement or super-position, one can solve some problems much more efficiently than with classical computers. One of the most striking examples is the factoring problem. This task is believed to be out of reach of classical computers as soon as the number of digits in the number to factor exceeds a certain limit. In this contribution, we present the basic notion of quantum computation and review the most common quantum algorithms discovered so far.

DOI
10.1142/9789812385253_0006

Related papers

Quantum Physics and Computers

Adriano Barenco

Recent theoretical results confirm that quantum theory provides the possibility of new ways of performing efficient calculations. The most striking example is the factoring problem. It has recently been shown that computers that exploit quantum features could factor large composite integers This task is believed to be out of reach of classical computers as soon as the number of digits in the number to factor exceeds a certain limit. The additional power of quantum computers comes from the possibility of employing a superposition of states, of following many distinct computation paths and of producing a final output that depends on the interference of all of them. This "quantum parallelism" outstrips by far any parallelism that can be thought of in classical computation and is responsible for the "exponential" speed-up of computation. Experimentally, however, it will be extremely difficult to "decouple" a quantum computer from its environment. Noise fluctuations due to the outside world...

•Dec 2, 1996•100 citations

Quantum physics and computers

Adriano Barenco

Recent theoretical results confirm that quantum theory provides the possibility of new ways of performing efficient calculations. The most striking example is the factoring problem. It has recently been shown that computers that exploit quantum features could factor large composite integers. This task is believed to be out of reach of classical computers as soon as the number of digits in the number to factor exceeds a certain limit. The additional power of quantum computers comes from the possibility of employing a superposition of states, of following many distinct computation paths and of producing a final output that depends on the interference of all of them. This ‘quantum parallelism’ outstrips by far any parallelism that can be thought of in classical computation and is responsible for the ‘exponential’ speed-up of computation. Experimentally, however, it will be extremely difficult to ‘decouple’ a quantum computer from its environment. Noise fluctuations due to the outside world, no matter how little, are sufficient to drastically reduce the performance of these new computing devices. To control the nefarious effects of this environmental noise, one needs to implement efficient error-correcting techniques.

arXiv:quant-ph/9612014•Contemporary Physics•Sep 1, 1996•124 citations

Tutorial: basic concepts in quantum circuits

John P. Hayes

Over the last decade a new way to compute has been defined which, unlike conventional methods, is based on quantum mechanics rather than classical physics. This fundamental change in paradigm can, in principle, solve some important and hitherto intractable problems such as prime factorization of large numbers. This tutorial presentation will review the basics of quantum computation and the design of circuits to implement quantum algorithms. The starting point is the notion of a quantum bit or qubit. Because of the superposition property of quantum states, n qubits can store 2n numbers simultaneously, implying a type of massive parallelism. Furthermore, quantum states allow powerful forms of interaction such as entanglement that have no classical counterparts. Qubits are fragile, however, and are altered by measurement; hence quantum circuits must follow very different rules from classical ones. The differences between quantum and classical logic circuits will be discussed and illustrated. Finally, the physical implementation of quantum devices will be considered, along with the prospects for practical quantum computers.

ACM/IEEE Design Automation Conference (DAC)•Jan 1, 2003•0 citations

Tutorial: basic concepts in quantum circuits

J.P. Hayes

Over the last decade a new way to compute has been defined which, unlike conventional methods, is based on quantum mechanics rather than classical physics. This fundamental change in paradigm can, in principle, solve some important and hitherto intractable problems such as prime factorization of large numbers. This tutorial presentation will review the basics of quantum computation and the design of circuits to implement quantum algorithms. The starting point is the notion of a quantum bit or qubit. Because of the superposition property of quantum states, n qubits can store 2n numbers simultaneously, implying a type of massive parallelism. Furthermore, quantum states allow powerful forms of interaction such as entanglement that have no classical counterparts. Qubits are fragile, however, and are altered by measurement; hence quantum circuits must follow very different rules from classical ones. The differences between quantum and classical logic circuits will be discussed and illustrated. Finally, the physical implementation of quantum devices will be considered, along with the prospects for practical quantum computers.

ACM/IEEE Design Automation Conference (DAC)•Mar 2, 2004•0 citations

Quantum algorithms for algebraic problems

Andrew M. Childs, Wim van Dam

Quantum computers can execute algorithms that dramatically outperform classical computation. As the best-known example, Shor discovered an efficient quantum algorithm for factoring integers, whereas factoring appears to be difficult for classical computers. Understanding what other computational problems can be solved significantly faster using quantum algorithms is one of the major challenges in the theory of quantum computation, and such algorithms motivate the formidable task of building a large-scale quantum computer. This article reviews the current state of quantum algorithms, focusing on algorithms with superpolynomial speedup over classical computation and, in particular, on problems with an algebraic flavor.

arXiv:0812.0380•Reviews of Modern Physics•Jan 15, 2010•379 citations

Quantum algorithms

In this chapter, we focus on quantum algorithms and the techniques underlying their construction. These algorithms take advantage of the basic properties of quantum mechanics, from the superposition principle to entanglement and interference effects, to solve certain computational problems much more efficiently than a classical computer. This includes basic problems of computer science: from the search of a marked item in an unstructured database (Grover’s algorithm) to integer factoring (Shor’s algorithm). The latter case provides a striking exponential speedup over the best known classical algorithms. After that, we discuss a third relevant class of quantum algorithms, the simulation of physical systems.

WORLD SCIENTIFIC eBooks•Dec 1, 2018•0 citations
When applied to computation, quantum mechanics opens completely new perspectives; by exploiting quantum mechanical features such as entanglement or super-position, one can solve some problems much more efficiently than with classical computers. One of the most striking examples is the factoring problem. This task is believed to be out of reach of classical computers as soon as the number of digits in the number to factor exceeds a certain limit. In this contribution, we present the basic notion of quantum computation and review the most common quantum algorithms discovered so far.
Recent theoretical results confirm that quantum theory provides the possibility of new ways of performing efficient calculations. The most striking example is the factoring problem. It has recently been shown that computers that exploit quantum features could factor large composite integers This task is believed to be out of reach of classical computers as soon as the number of digits in the number to factor exceeds a certain limit. The additional power of quantum computers comes from the possibility of employing a superposition of states, of following many distinct computation paths and of producing a final output that depends on the interference of all of them. This "quantum parallelism" outstrips by far any parallelism that can be thought of in classical computation and is responsible for the "exponential" speed-up of computation. Experimentally, however, it will be extremely difficult to "decouple" a quantum computer from its environment. Noise fluctuations due to the outside world...
Recent theoretical results confirm that quantum theory provides the possibility of new ways of performing efficient calculations. The most striking example is the factoring problem. It has recently been shown that computers that exploit quantum features could factor large composite integers. This task is believed to be out of reach of classical computers as soon as the number of digits in the number to factor exceeds a certain limit. The additional power of quantum computers comes from the possibility of employing a superposition of states, of following many distinct computation paths and of producing a final output that depends on the interference of all of them. This ‘quantum parallelism’ outstrips by far any parallelism that can be thought of in classical computation and is responsible for the ‘exponential’ speed-up of computation. Experimentally, however, it will be extremely difficult to ‘decouple’ a quantum computer from its environment. Noise fluctuations due to the outside world, no matter how little, are sufficient to drastically reduce the performance of these new computing devices. To control the nefarious effects of this environmental noise, one needs to implement efficient error-correcting techniques.
Over the last decade a new way to compute has been defined which, unlike conventional methods, is based on quantum mechanics rather than classical physics. This fundamental change in paradigm can, in principle, solve some important and hitherto intractable problems such as prime factorization of large numbers. This tutorial presentation will review the basics of quantum computation and the design of circuits to implement quantum algorithms. The starting point is the notion of a quantum bit or qubit. Because of the superposition property of quantum states, n qubits can store 2n numbers simultaneously, implying a type of massive parallelism. Furthermore, quantum states allow powerful forms of interaction such as entanglement that have no classical counterparts. Qubits are fragile, however, and are altered by measurement; hence quantum circuits must follow very different rules from classical ones. The differences between quantum and classical logic circuits will be discussed and illustrated. Finally, the physical implementation of quantum devices will be considered, along with the prospects for practical quantum computers.
Over the last decade a new way to compute has been defined which, unlike conventional methods, is based on quantum mechanics rather than classical physics. This fundamental change in paradigm can, in principle, solve some important and hitherto intractable problems such as prime factorization of large numbers. This tutorial presentation will review the basics of quantum computation and the design of circuits to implement quantum algorithms. The starting point is the notion of a quantum bit or qubit. Because of the superposition property of quantum states, n qubits can store 2n numbers simultaneously, implying a type of massive parallelism. Furthermore, quantum states allow powerful forms of interaction such as entanglement that have no classical counterparts. Qubits are fragile, however, and are altered by measurement; hence quantum circuits must follow very different rules from classical ones. The differences between quantum and classical logic circuits will be discussed and illustrated. Finally, the physical implementation of quantum devices will be considered, along with the prospects for practical quantum computers.
Quantum computers can execute algorithms that dramatically outperform classical computation. As the best-known example, Shor discovered an efficient quantum algorithm for factoring integers, whereas factoring appears to be difficult for classical computers. Understanding what other computational problems can be solved significantly faster using quantum algorithms is one of the major challenges in the theory of quantum computation, and such algorithms motivate the formidable task of building a large-scale quantum computer. This article reviews the current state of quantum algorithms, focusing on algorithms with superpolynomial speedup over classical computation and, in particular, on problems with an algebraic flavor.
In this chapter, we focus on quantum algorithms and the techniques underlying their construction. These algorithms take advantage of the basic properties of quantum mechanics, from the superposition principle to entanglement and interference effects, to solve certain computational problems much more efficiently than a classical computer. This includes basic problems of computer science: from the search of a marked item in an unstructured database (Grover’s algorithm) to integer factoring (Shor’s algorithm). The latter case provides a striking exponential speedup over the best known classical algorithms. After that, we discuss a third relevant class of quantum algorithms, the simulation of physical systems.