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

Wiley eBooks

Quantum Circuits

Malek Benslama, Achour Benslama, Skander Aris

Published Jan 14, 2017• 0 citations
Publisher

Abstract

Quantum circuits can be reversible in so far that the initial state can be determined from the final state. The reasoning always begins from the space of the states, which is a purely quantum space. The Toffoli gates are reversible and universal primitive functions, which mean that any reversible function can be constructed in terms of Toffoli gates. Any reversible circuit can be constructed from the Toffoli gate; it acts as NON gate with dual control. In quantum calculation, the quantum finite automaton or quantum state machine is the quantum analogue of the probabilistic automaton or Markov decision process. It is linked to the quantum computer in a similar way to the finite automaton, which is linked to the Turing machine. A quantum finite automaton can be understood as the quantization of finite sub-offsets or as a quantization of Markov chains.

DOI
10.1002/9781119332510.ch4

Related papers

Dual Toffoli and Peres-reversible gates

Claudio Moraga

The paper introduces dual Toffoli and Peres reversible gates, which operate under disjunctive control, and shows their functionality based on the Barenco et al. quantum model. Both uniform and mixed polarity are considered for the controls. Rewriting rules are presented, which provide a possible reduction of the number of gates and quantum cost of reversible (sub)circuits using standard Toffoli or Peres gates. Finally, a Clifford+T realization of a dual Toffoli and a dual Peres gate is shown, which may be used when mapping reversible circuits to the IBM quantum computers.

arXiv:2011.01746•Nov 1, 2020•0 citations

Quantum reversibility and a new model of quantum automaton

Massimo Pica Ciamarra

This article is an attempt to generalize the classical theory of reversible computing, principally developed by Bennet [IBM J. Res. Develop., 17(1973)] and by Fredkin and Toffoli [Internat. J. Theoret. Phys., 21(1982)], to the quantum case. This is a fundamental step towards the construction of a quantum computer because a time efficient quantum computation is a reversible physical process. The paper is organized as follows. The first section reviews the classical theory of reversible computing. In the second section it is showed that the designs used in the classical framework to decrease the consumption of space cannot be generalized to the quantum case; it is also suggested that quantum computing is generally more demanding of space than classical computing. In the last section a new model of fully quantum and reversible automaton is proposed. The computational power of this automaton is at least equal to that of classical automata. Some conclusion are drawn in the last section.

arXiv:quant-ph/0102104•Feb 21, 2001•1 citation

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

Designing of Reversible Functions in Classical and Quantum Domains

Andrzej Skorupski, Ryszard S. Romaniuk

First sections of the paper contain some considerations relevant to the reversibility of quantum gates. The Solovay-Kitayev theorem shows that using proper set of quantum gates one can build a quantum version of the nondeterministic Turing machine. On the other hand the Gottesmann-Knill theorem shows the possibility to simulate the quantum machine consisting of only Clifford/Pauli group of gates. This paper presents also an original method of designing the reversible functions. This method is intended for the most popular gate set with three types of gates CNT (Control, NOT and Toffoli). The presented algorithm leads to cascade with minimal number CNT gates. This solution is called optimal reversible circuits. The paper is organized as follows. Section 5 recalls basic concepts of reversible logic. Section 6 contain short description of CNT set of the reversible gates. In Section 7 is presented form of result of designing as the cascade of gates. Section 8 describes the algorithm and section 9 simple example.

International Journal of Electronics and Telecommunications•Jun 25, 2024•0 citations

Aspects of Reversible and Quantum Computing in a -Valued Domain

Claudio Moraga

This paper presents basic aspects of non-binary reversible and quantum computing in a p-valued environment, since there are no physical reasons for quantum computing to be necessarily binary. A “quantum technology” is not yet available, but different alternatives at the level of laboratory experiments are promising. A theoretical background is needed to face the challenge of designing circuits for quantum computing. Pauli matrices are introduced in the p-valued domain and their properties are explained. The Vilenkin-Chrestenson matrix is shown to produce superposition of states. Entanglement of quantum states in the p-valued environment is introduced and its measurement effect is illustrated. It is shown that in the p-valued domain, the binary Toffoli gate may be given different generalizations with different functionalities. An ancillary-free realization of a new generalized p-valued Toffoli gate based on Muthukrishnan-Stroud elementary gates is presented, its functionality is extended to two kinds of control, and a proof of its performance is given.

IEEE Journal on Emerging and Selected Topics in Circuits and Systems•Mar 1, 2016•4 citations

Quantum automata and quantum computing

Marats Golovkins

Quantum finite automata were introduced by C.Moore and J.P.Crutchfield in [MC 97] and by A.Kondacs and J.Watrous in [KW 97]. This notion is not a generalization of the deterministic finite automata, but rather a generalization of deterministic reversible (permutation) automata. In [AF 98] A.Ambainis and R.Freivalds raised the question what kind of probabilistic automata can be viewed as a special case of quantum finite automata. To answer that question and study relationship between quantum finite automata and probabilistic finite automata, we introduce a notion of probabilistic reversible automata (PRA, or doubly stochastic automata). We give the necessary condition for a language to be recognized by PRA. We find that there is a strong relationship between different possible models of PRA and corresponding models of quantum finite automata. In these thesis we regard quantum automata, probabilistic reversible and deterministic reversible automata as reversible automata. At least two non-equivalent definitions of language recognition are used for one-way reversible finite automata in various papers. Both of these definitions have their own advantages and disadvantages, summarized in our classification of one-way reversible automata. Further, we introduce a notion of quantum finite multitape automata and prove that there is a language recognized by a quantum finite multitape automaton but not by deterministic finite multitape automata. Additionally we discover unexpected probabilistic automata recognizing complicated languages. Finally, we revise the concept of quantum pushdown automata (QPA), first introduced by C.Moore and J.P.Cruthchfield in [MC 97]. We give the definition of QPA in a non-equivalent way, including unitarity criteria, by using the definition of quantum finite automata of [KW 97]. It is established that the unitary criteria of QPA are not equivalent to the corresponding unitary criteria of quantum Turing machines [BV 97]. We show that QPA can recognize every regular language. We also present some simple non-context-free languages recognized by QPA (hence not recognizable by deterministic and nondeterministic pushdown automata).

•Jan 1, 2002•0 citations
Quantum circuits can be reversible in so far that the initial state can be determined from the final state. The reasoning always begins from the space of the states, which is a purely quantum space. The Toffoli gates are reversible and universal primitive functions, which mean that any reversible function can be constructed in terms of Toffoli gates. Any reversible circuit can be constructed from the Toffoli gate; it acts as NON gate with dual control. In quantum calculation, the quantum finite automaton or quantum state machine is the quantum analogue of the probabilistic automaton or Markov decision process. It is linked to the quantum computer in a similar way to the finite automaton, which is linked to the Turing machine. A quantum finite automaton can be understood as the quantization of finite sub-offsets or as a quantization of Markov chains.
The paper introduces dual Toffoli and Peres reversible gates, which operate under disjunctive control, and shows their functionality based on the Barenco et al. quantum model. Both uniform and mixed polarity are considered for the controls. Rewriting rules are presented, which provide a possible reduction of the number of gates and quantum cost of reversible (sub)circuits using standard Toffoli or Peres gates. Finally, a Clifford+T realization of a dual Toffoli and a dual Peres gate is shown, which may be used when mapping reversible circuits to the IBM quantum computers.
This article is an attempt to generalize the classical theory of reversible computing, principally developed by Bennet [IBM J. Res. Develop., 17(1973)] and by Fredkin and Toffoli [Internat. J. Theoret. Phys., 21(1982)], to the quantum case. This is a fundamental step towards the construction of a quantum computer because a time efficient quantum computation is a reversible physical process. The paper is organized as follows. The first section reviews the classical theory of reversible computing. In the second section it is showed that the designs used in the classical framework to decrease the consumption of space cannot be generalized to the quantum case; it is also suggested that quantum computing is generally more demanding of space than classical computing. In the last section a new model of fully quantum and reversible automaton is proposed. The computational power of this automaton is at least equal to that of classical automata. Some conclusion are drawn in the last section.
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.
First sections of the paper contain some considerations relevant to the reversibility of quantum gates. The Solovay-Kitayev theorem shows that using proper set of quantum gates one can build a quantum version of the nondeterministic Turing machine. On the other hand the Gottesmann-Knill theorem shows the possibility to simulate the quantum machine consisting of only Clifford/Pauli group of gates. This paper presents also an original method of designing the reversible functions. This method is intended for the most popular gate set with three types of gates CNT (Control, NOT and Toffoli). The presented algorithm leads to cascade with minimal number CNT gates. This solution is called optimal reversible circuits. The paper is organized as follows. Section 5 recalls basic concepts of reversible logic. Section 6 contain short description of CNT set of the reversible gates. In Section 7 is presented form of result of designing as the cascade of gates. Section 8 describes the algorithm and section 9 simple example.
This paper presents basic aspects of non-binary reversible and quantum computing in a p-valued environment, since there are no physical reasons for quantum computing to be necessarily binary. A “quantum technology” is not yet available, but different alternatives at the level of laboratory experiments are promising. A theoretical background is needed to face the challenge of designing circuits for quantum computing. Pauli matrices are introduced in the p-valued domain and their properties are explained. The Vilenkin-Chrestenson matrix is shown to produce superposition of states. Entanglement of quantum states in the p-valued environment is introduced and its measurement effect is illustrated. It is shown that in the p-valued domain, the binary Toffoli gate may be given different generalizations with different functionalities. An ancillary-free realization of a new generalized p-valued Toffoli gate based on Muthukrishnan-Stroud elementary gates is presented, its functionality is extended to two kinds of control, and a proof of its performance is given.
Quantum finite automata were introduced by C.Moore and J.P.Crutchfield in [MC 97] and by A.Kondacs and J.Watrous in [KW 97]. This notion is not a generalization of the deterministic finite automata, but rather a generalization of deterministic reversible (permutation) automata. In [AF 98] A.Ambainis and R.Freivalds raised the question what kind of probabilistic automata can be viewed as a special case of quantum finite automata. To answer that question and study relationship between quantum finite automata and probabilistic finite automata, we introduce a notion of probabilistic reversible automata (PRA, or doubly stochastic automata). We give the necessary condition for a language to be recognized by PRA. We find that there is a strong relationship between different possible models of PRA and corresponding models of quantum finite automata. In these thesis we regard quantum automata, probabilistic reversible and deterministic reversible automata as reversible automata. At least two non-equivalent definitions of language recognition are used for one-way reversible finite automata in various papers. Both of these definitions have their own advantages and disadvantages, summarized in our classification of one-way reversible automata. Further, we introduce a notion of quantum finite multitape automata and prove that there is a language recognized by a quantum finite multitape automaton but not by deterministic finite multitape automata. Additionally we discover unexpected probabilistic automata recognizing complicated languages. Finally, we revise the concept of quantum pushdown automata (QPA), first introduced by C.Moore and J.P.Cruthchfield in [MC 97]. We give the definition of QPA in a non-equivalent way, including unitarity criteria, by using the definition of quantum finite automata of [KW 97]. It is established that the unitary criteria of QPA are not equivalent to the corresponding unitary criteria of quantum Turing machines [BV 97]. We show that QPA can recognize every regular language. We also present some simple non-context-free languages recognized by QPA (hence not recognizable by deterministic and nondeterministic pushdown automata).