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:cs/0304008 · WORLD SCIENTIFIC eBooks

A PHYSICS-FREE INTRODUCTION TO THE QUANTUM COMPUTATION MODEL

Stephen Fenner

Published Apr 1, 2004• 4 citations
arXivHTMLPDF

Abstract

This article defines and proves basic properties of the standard quantum circuit model of computation. The model is developed abstractly in close analogy with (classical) deterministic and probabilistic circuits, without recourse to any physical concepts or principles. It is intended as a primer for theoretical computer scientists who do not know--and perhaps do not care to know--any physics.

DOI
10.1142/9789812562494_0010

Related papers

Quantum computation

This chapter introduces the basic principles of quantum computation. We shall adhere to the quantum circuit model of computation, with which it is easy to work and which is close to physical implementations. We shall not discuss the more abstract quantum Turing machine model, which, however, has been shown to be equivalent to the circuit model. The elementary unit of quantum information and the basic building block of quantum computation is the qubit, a two-level quantum system that can be prepared, manipulated and measured in a controlled way. A quantum computer can be seen as a collection of n qubits and therefore its wave function resides in a 2 n -dimensional complex Hilbert space. As far as coupling to the environment may be neglected, its evolution in time is unitary and governed by the Schrödinger equation. A quantum computation is composed of three basic steps: preparation of the input state, implementation of the desired unitary transformation acting on this state and measurement of the output state. The output of the measurement process is inherently probabilistic and the probabilities of the different possible outputs are set by the basic postulates of quantum mechanics. Therefore, in a quantum algorithm we must, in general, repeat several times the algorithm to obtain the correct solution of our problem with probability as close to one as desired. In this sense, quantum algorithms are analogous to classical probabilistic algorithms. However, the superposition principle and quantum entanglement open up new possibilities for computation. Quantum computers are potentially more powerful than classical (deterministic or probabilistic) computers due to quantum interference and entanglement. We show that, analogously to classical computation, there exists a small set of gates that are universal, that is, any unitary transformation can be decomposed into a sequence of these gates. We then discuss the implementation of the basic Boolean functions and arithmetic operations on a quantum computer.

WORLD SCIENTIFIC eBooks•Dec 1, 2018•0 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 computing from a mathematical perspective: a description of the quantum circuit model

Joaquín Ossorio-Castillo, José M. Tornero

This paper is an essentially self-contained and rigorous description of the fundamental principles of quantum computing from a mathematical perspective. It is intended to help mathematicians who want to get a grasp of this quickly growing discipline and find themselves taken aback by the language gap between mathematics and the pioneering fields on the matter: computer science and quantum physics. A first version of this paper was originally published at arXiv in October 2018. Minor corrections added on Spring 2025.

arXiv:1810.08277•Oct 16, 2018•7 citations

The Leap from Classical to Quantum

Noson S. Yanofsky, Mirco A. Mannucci

Before we formally present quantum mechanics in all its wonders, we shall spend time providing some basic intuitions behind its core methods and ideas. Realizing that computer scientists feel comfortable with graphs and matrices, we shall cast quantum mechanical ideas in graph-theoretic and matrix-theoretic terms. Everyone who has taken a class in discrete structures knows how to represent a (weighted) graph as an adjacency matrix. We shall take this basic idea and generalize it in several straightforward ways. While doing this, we shall present a few concepts that are at the very core of quantum mechanics. In Section 3.1, the graphs are without weights. This will model classical deterministic systems. In Section 3.2, the graphs are weighted with real numbers. This will model classical probabilistic systems. In Section 3.3, the graphs are weighted with complex numbers and will model quantum systems. We conclude Section 3.3 with a computer science/graph-theoretic version of the double-slit experiment. This is perhaps the most important experiment in quantum mechanics. Section 3.4 discusses ways of combining systems to yield larger systems.

Cambridge University Press eBooks•Aug 11, 2008•0 citations

Basics of Quantum Computation (Part 1)

Elemér Elad Rosinger

The aim of this textbook is to bridge in regard of quantum computation what proves to be a considerable threshold even to the usual science trained readership between the level of science popularization, and on the other hand, the presently available more encyclopedic textbooks. In this respect the present textbook is aimed to be a short, simple, rigorous and direct introduction, addressing itself only to quantum computation proper.

arXiv:quant-ph/0407064•Jul 8, 2004•3 citations
This article defines and proves basic properties of the standard quantum circuit model of computation. The model is developed abstractly in close analogy with (classical) deterministic and probabilistic circuits, without recourse to any physical concepts or principles. It is intended as a primer for theoretical computer scientists who do not know--and perhaps do not care to know--any physics.
This chapter introduces the basic principles of quantum computation. We shall adhere to the quantum circuit model of computation, with which it is easy to work and which is close to physical implementations. We shall not discuss the more abstract quantum Turing machine model, which, however, has been shown to be equivalent to the circuit model. The elementary unit of quantum information and the basic building block of quantum computation is the qubit, a two-level quantum system that can be prepared, manipulated and measured in a controlled way. A quantum computer can be seen as a collection of n qubits and therefore its wave function resides in a 2 n -dimensional complex Hilbert space. As far as coupling to the environment may be neglected, its evolution in time is unitary and governed by the Schrödinger equation. A quantum computation is composed of three basic steps: preparation of the input state, implementation of the desired unitary transformation acting on this state and measurement of the output state. The output of the measurement process is inherently probabilistic and the probabilities of the different possible outputs are set by the basic postulates of quantum mechanics. Therefore, in a quantum algorithm we must, in general, repeat several times the algorithm to obtain the correct solution of our problem with probability as close to one as desired. In this sense, quantum algorithms are analogous to classical probabilistic algorithms. However, the superposition principle and quantum entanglement open up new possibilities for computation. Quantum computers are potentially more powerful than classical (deterministic or probabilistic) computers due to quantum interference and entanglement. We show that, analogously to classical computation, there exists a small set of gates that are universal, that is, any unitary transformation can be decomposed into a sequence of these gates. We then discuss the implementation of the basic Boolean functions and arithmetic operations on a quantum computer.
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.
This paper is an essentially self-contained and rigorous description of the fundamental principles of quantum computing from a mathematical perspective. It is intended to help mathematicians who want to get a grasp of this quickly growing discipline and find themselves taken aback by the language gap between mathematics and the pioneering fields on the matter: computer science and quantum physics. A first version of this paper was originally published at arXiv in October 2018. Minor corrections added on Spring 2025.
Before we formally present quantum mechanics in all its wonders, we shall spend time providing some basic intuitions behind its core methods and ideas. Realizing that computer scientists feel comfortable with graphs and matrices, we shall cast quantum mechanical ideas in graph-theoretic and matrix-theoretic terms. Everyone who has taken a class in discrete structures knows how to represent a (weighted) graph as an adjacency matrix. We shall take this basic idea and generalize it in several straightforward ways. While doing this, we shall present a few concepts that are at the very core of quantum mechanics. In Section 3.1, the graphs are without weights. This will model classical deterministic systems. In Section 3.2, the graphs are weighted with real numbers. This will model classical probabilistic systems. In Section 3.3, the graphs are weighted with complex numbers and will model quantum systems. We conclude Section 3.3 with a computer science/graph-theoretic version of the double-slit experiment. This is perhaps the most important experiment in quantum mechanics. Section 3.4 discusses ways of combining systems to yield larger systems.