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• 3 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

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

The Leap from Classical to Quantum

Noson S. Yanofsky, Mirco A. Mannucci

Everyone has lost their marbles! Anonymous 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. Throughout this chapter, we first present an idea in terms of a toy model, then generalize it to an abstract point, and finally discuss its connection with quantum mechanics, before moving on to the next idea.

Cambridge University Press eBooks•Aug 11, 2008•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•1 citation

De computatione quantica

Gilles Brassard A, José M. Fernandez

This thesis covers the topic of Quantum Computation, in both its theoretical and experimental aspects. The Theory of Quantum Computing is an extension of the standard Theory of Computation inspired by the principles of Quantum Mechanics. The discovery of efficient quantum algorithms for problems for which no efficient classical algorithms are known challenges the Strong Church-Turing Thesis, which states that all computational models are essentially equivalent in terms of what they can compute and how efficiently they can do so. In Part I of this thesis, we study the nature of this difference. We first introduce a general and simplified framework for characterising the essence of a quantum theory, in contrast with a deterministic or a probabilistic theory. We put forth the thesis that the most fundamental axioms are those related to measurement, from which these differences emanate. We cover some variations on these theories, and show some interesting structural relationships between them. For example, the only models which can be simultaneously quantum and probabilistic are the deterministic ones. We then use this meta-model to re-introduce in a succinct and uniform manner the deterministic, probabilistic and quantum versions of the Turing Machine and circuit computational models. Moreover, we generalise the circuit model on arbitrary semirings. We thus succeed in providing a new classification of existing complexity classes by varying the semirings and vector norms with which their vector space of states is defined. In particular, the standard models of deterministic, probabilistic, and quantum computing can be characterised (with the same norm) by defining circuits on the boolean algebra, the positive rational or reals, and the rational or reals, respectively. We further explore this model with other non-standard semirings. We show that quaternion based models are equivalent to quantum computation. Finally, we strengthen this “algebraic hierarchy” by using the tensor formula formalism to construct a family of complete (or promise complete) problems for the corresponding complexity classes. Part II concerns experimental Quantum Computing by Nuclear Magnetic Resonance (NMR). An important obstacle in this approach is the inability to properly initialise the quantum register, which is related to the signal-to-noise problem in NMR spectroscopy. One of the most promising techniques to solve it is Algorithmic Cooling, a generalisation of the polarisation transfer techniques already used by NMR spectroscopists. We discuss the traditional adiabatic approaches and their limitations. We describe a variation on this technique, the non-adiabatic approach, which uses the environment in order to cool beyond these limits. In particular, we provide a new, efficient non-adiabatic cooling algorithm which could achieve near-zero spin temperatures in liquid-state NMR already with more reasonably sized registers (30–60 spins). Finally, we report on the successful laboratory realisation of the first ever non-adiabatic cooling experiment. This constitutes, we hope, the first step towards the fully fledged development of this promising technique, with applications far beyond NMR-based Quantum Computing.

•Jan 1, 2004•7 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•1 citation

A Short Introduction to Quantum Computing for Physicists

Oswaldo Zapata

These notes provide an introduction to standard topics on quantum computation and communication for those who already have a basic knowledge of quantum mechanics. The main target audience are professional physicists as well as advanced students of physics; however, engineers and computer scientists may also benefit from them.

arXiv:2306.09388•Jun 15, 2023•0 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.
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.
Everyone has lost their marbles! Anonymous 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. Throughout this chapter, we first present an idea in terms of a toy model, then generalize it to an abstract point, and finally discuss its connection with quantum mechanics, before moving on to the next idea.
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.
This thesis covers the topic of Quantum Computation, in both its theoretical and experimental aspects. The Theory of Quantum Computing is an extension of the standard Theory of Computation inspired by the principles of Quantum Mechanics. The discovery of efficient quantum algorithms for problems for which no efficient classical algorithms are known challenges the Strong Church-Turing Thesis, which states that all computational models are essentially equivalent in terms of what they can compute and how efficiently they can do so. In Part I of this thesis, we study the nature of this difference. We first introduce a general and simplified framework for characterising the essence of a quantum theory, in contrast with a deterministic or a probabilistic theory. We put forth the thesis that the most fundamental axioms are those related to measurement, from which these differences emanate. We cover some variations on these theories, and show some interesting structural relationships between them. For example, the only models which can be simultaneously quantum and probabilistic are the deterministic ones. We then use this meta-model to re-introduce in a succinct and uniform manner the deterministic, probabilistic and quantum versions of the Turing Machine and circuit computational models. Moreover, we generalise the circuit model on arbitrary semirings. We thus succeed in providing a new classification of existing complexity classes by varying the semirings and vector norms with which their vector space of states is defined. In particular, the standard models of deterministic, probabilistic, and quantum computing can be characterised (with the same norm) by defining circuits on the boolean algebra, the positive rational or reals, and the rational or reals, respectively. We further explore this model with other non-standard semirings. We show that quaternion based models are equivalent to quantum computation. Finally, we strengthen this “algebraic hierarchy” by using the tensor formula formalism to construct a family of complete (or promise complete) problems for the corresponding complexity classes. Part II concerns experimental Quantum Computing by Nuclear Magnetic Resonance (NMR). An important obstacle in this approach is the inability to properly initialise the quantum register, which is related to the signal-to-noise problem in NMR spectroscopy. One of the most promising techniques to solve it is Algorithmic Cooling, a generalisation of the polarisation transfer techniques already used by NMR spectroscopists. We discuss the traditional adiabatic approaches and their limitations. We describe a variation on this technique, the non-adiabatic approach, which uses the environment in order to cool beyond these limits. In particular, we provide a new, efficient non-adiabatic cooling algorithm which could achieve near-zero spin temperatures in liquid-state NMR already with more reasonably sized registers (30–60 spins). Finally, we report on the successful laboratory realisation of the first ever non-adiabatic cooling experiment. This constitutes, we hope, the first step towards the fully fledged development of this promising technique, with applications far beyond NMR-based Quantum Computing.