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

ACM SIGACT News

Guest Column

Carlo Mereghetti, Beatrice Palano

Published Oct 17, 2021• 4 citations
Publisher

Abstract

Quantum computing is a prolific research area, halfway between physics and computer science [27, 29, 52]. Most likely, its origins may be dated back to 70's, when some works on quantum information began to appear (see, e.g., [34, 37]). In early 80's, R.P. Feynman suggested that the computational power of quantum mechanical processes might be beyond that of traditional computation models [25]. Almost at the same time, P. Benioff already proved that such processes are at least as powerful as Turing machines [9]. In 1985, D. Deutsch [22] proposed the notion of a quantum Turing machine as a physically realizable model for a quantum computer. From the point of view of structural complexity, E. Bernstein and U. Vazirani introduced in [20] the class BQP of problems solvable in polynomial time on quantum Turing machines, focusing attention on relations with the corresponding deterministic and probabilistic classes P and BPP, respectively. Several works in the literature explored classical issues in complexity theory from the quantum paradigm perspective (see, e.g., [7, 60, 61]).

DOI
10.1145/3494656.3494666

Related papers

An Introduction to Quantum Computing and Information

David K. Ferry

The idea of using quantum mechanics to provide more power than that available from classical computers seems to have begun around 1981–82 ( Benioff, 1982 ), but Deutsch (1985) put the concept on a sounder footing a short time later when he reformulated the Turing (1937) thesis with the assertion that every finite realizable physical system can be perfectly simulated by a universal model computing machine operating by finite means. However, he asserted that the output of a quantum machine, although fully determined by the input state, is not an observable itself. Hence, the user must provide some cleverness if this state is to be determined. Benioff pointed out the need for the quantum state to experience interference, some indeterminism, and was what we would today call an entangled state. He also realized that non-dissipative evolution was unphysical, so immediately it became clear that a great deal of effort would be required to minimize the decoherence of the physical states. Deutsch (1989) then provided some input as to what type of states or systems might be usable in this process. Jozsa (1991) mathematically showed that one could associate a quantum state to each function that one desired to evaluate, and that this should lead to a rapid solution of problems via the quantum computer ( Deutsch and Jozsa, 1992 ). Since these introductions, the world has progressed rapidly into a determined search for applications of quantum mechanics throughout the information processing world.

CRC Press eBooks•Aug 19, 2026•0 citations

THE EVOLUTION OF COMPUTATIONAL PARADIGMS FROM PROBABILISTIC TECHNIQUES TO QUANTUM QUERY ALGORITHMS

P. Kiran Goud

The evolution of computational theory from deterministic frameworks to probabilistic and quantum paradigms has fundamentally transformed the understanding of algorithmic efficiency and computational complexity. Clas sical deterministic computation, grounded in the Church–Turing thesis and Boolean circuit models, provided the original foundation for analyzing computational problems. However, the introduction of randomized algorithms expanded this framework by incorporating probabilistic decision-making, enabling substantial improvements in approximation, primality testing, and complexity reduction through classes such as BPP, RP, and ZPP. Building upon these probabilistic foundations, quantum computation introduced a radically different model based on superposition, interference, entanglement, and unitary evolution in Hilbert space. This report examines the structural and mathematical transition from classical circuit complexity to quantum query algorithms, em phasizing how quantum interference enables global information extraction beyond the capabilities of determinis tic and randomized methods. The work explores the theoretical architecture of universal gate sets, reversibility constraints, randomized complexity classes, and the probabilistic method before advancing toward foundational quantum algorithms. Particular focus is placed on the Deutsch, Deutsch–Jozsa, Bernstein–Vazirani, and Simon algorithms, which collectively demonstrate increasingly powerful forms of quantum advantage. Deutsch’s algorithm establishes interference-based computation as a valid computational resource, while the Deutsch–Jozsa algorithm provides an exponential deterministic query separation between classical and quantum models. The Bernstein–Vazirani algorithm illustrates efficient hidden-string extraction through Fourier decoding, and Simon’s algorithm intro duces hidden subgroup structures and exponential oracle separations that directly inspired Shor’s factoring algo rithm. The report further analyzes the algebraic structure of Simon’s algorithm through Gaussian elimination over GF(2), hidden XOR periodicity, and coset-state superpositions. In addition, the study examines advanced quantum phenomena including interaction-free measurement in the Elitzur–Vaidman bomb-testing protocol, quantum teleportation via entanglement, and the broader implications of complexity separations involving BQP, BPP, and PSPACE. By synthesizing classical probabilistic techniques with quantum query complexity, the report demonstrates how quantum computation transforms computational paradigms from local deterministic evaluation to global interference-driven information processing. These foun dational principles continue to guide modern developments in quantum algorithms, quantum cryptanalysis, and fault-tolerant quantum hardware within the Noisy Intermediate-Scale Quantum (NISQ) era.

Iterative International Publishers eBooks•May 1, 2026•0 citations

Computational models

Riccardo Manenti, Mário Motta

Abstract In this chapter, we introduce the definitions of automata Turing machines. We present different flavors of Turing machines including deterministic, probabilistic, and multi-tape machines. We present several complexity classes, i.e. collections of problems that can be solved by a machine with similar resources, including the P and NP classes. We present the Church-Turing thesis, which states that if a problem can be solved by a physical machine, then it can also be solved by any deterministic Turing machine. In the last part of the chapter, we introduce quantum Turing machines and the quantum circuit model. We study the complexity class BQP. This is the class of problems that can be solved by a quantum computer with polynomial resources and a small error probability. Finally, we introduce QMA, the quantum version of the complexity class NP. We present the k-LOCAL problem, and we show that this problem is in QMA

•Aug 25, 2023•0 citations

Special Issue “Quantum computation complexity theory and quantum network theory” (Preface)

Junde Wu

International Journal of Theoretical Physics•Jun 2, 2021•0 citations

Brief History and Overview of the Main Ideas for Quantum Computing

M. I. Dyakonov

SpringerBriefs in physics•Jan 1, 2020•0 citations

A critical overview on Quantum Computing

Saptarshi Sahoo, Amit Kumar Mandal, Pijus Kanti Samanta +2 more

Quantum Computing and Quantum Information Science seem very promising and developing rapidly since its inception in early 1980s by Paul Benioff with the proposal of quantum mechanical model of the Turing machine and later By Richard Feynman and Yuri Manin for the proposal of a quantum computers for simulating various problems that classical computer could not. Quantum computers have a computational advantage for some problems, over classical computers and most applications are trying to use an efficient combination of classical and quantum computers like Shor’s factoring algorithm. Other areas that are expected to be benefitted from quantum computing are Machine Learning and deep learning, molecular biology, genomics and cancer research, space exploration, atomic and nuclear research and macro-economic forecasting. This paper represents a brief overview of the state of art of quantum computing and quantum information science with discussions of various theoretical and experimental aspects adopted by the researchers.

Journal of quantum computing•Jan 1, 2020•17 citations
Quantum computing is a prolific research area, halfway between physics and computer science [27, 29, 52]. Most likely, its origins may be dated back to 70's, when some works on quantum information began to appear (see, e.g., [34, 37]). In early 80's, R.P. Feynman suggested that the computational power of quantum mechanical processes might be beyond that of traditional computation models [25]. Almost at the same time, P. Benioff already proved that such processes are at least as powerful as Turing machines [9]. In 1985, D. Deutsch [22] proposed the notion of a quantum Turing machine as a physically realizable model for a quantum computer. From the point of view of structural complexity, E. Bernstein and U. Vazirani introduced in [20] the class BQP of problems solvable in polynomial time on quantum Turing machines, focusing attention on relations with the corresponding deterministic and probabilistic classes P and BPP, respectively. Several works in the literature explored classical issues in complexity theory from the quantum paradigm perspective (see, e.g., [7, 60, 61]).
The idea of using quantum mechanics to provide more power than that available from classical computers seems to have begun around 1981–82 ( Benioff, 1982 ), but Deutsch (1985) put the concept on a sounder footing a short time later when he reformulated the Turing (1937) thesis with the assertion that every finite realizable physical system can be perfectly simulated by a universal model computing machine operating by finite means. However, he asserted that the output of a quantum machine, although fully determined by the input state, is not an observable itself. Hence, the user must provide some cleverness if this state is to be determined. Benioff pointed out the need for the quantum state to experience interference, some indeterminism, and was what we would today call an entangled state. He also realized that non-dissipative evolution was unphysical, so immediately it became clear that a great deal of effort would be required to minimize the decoherence of the physical states. Deutsch (1989) then provided some input as to what type of states or systems might be usable in this process. Jozsa (1991) mathematically showed that one could associate a quantum state to each function that one desired to evaluate, and that this should lead to a rapid solution of problems via the quantum computer ( Deutsch and Jozsa, 1992 ). Since these introductions, the world has progressed rapidly into a determined search for applications of quantum mechanics throughout the information processing world.
The evolution of computational theory from deterministic frameworks to probabilistic and quantum paradigms has fundamentally transformed the understanding of algorithmic efficiency and computational complexity. Clas sical deterministic computation, grounded in the Church–Turing thesis and Boolean circuit models, provided the original foundation for analyzing computational problems. However, the introduction of randomized algorithms expanded this framework by incorporating probabilistic decision-making, enabling substantial improvements in approximation, primality testing, and complexity reduction through classes such as BPP, RP, and ZPP. Building upon these probabilistic foundations, quantum computation introduced a radically different model based on superposition, interference, entanglement, and unitary evolution in Hilbert space. This report examines the structural and mathematical transition from classical circuit complexity to quantum query algorithms, em phasizing how quantum interference enables global information extraction beyond the capabilities of determinis tic and randomized methods. The work explores the theoretical architecture of universal gate sets, reversibility constraints, randomized complexity classes, and the probabilistic method before advancing toward foundational quantum algorithms. Particular focus is placed on the Deutsch, Deutsch–Jozsa, Bernstein–Vazirani, and Simon algorithms, which collectively demonstrate increasingly powerful forms of quantum advantage. Deutsch’s algorithm establishes interference-based computation as a valid computational resource, while the Deutsch–Jozsa algorithm provides an exponential deterministic query separation between classical and quantum models. The Bernstein–Vazirani algorithm illustrates efficient hidden-string extraction through Fourier decoding, and Simon’s algorithm intro duces hidden subgroup structures and exponential oracle separations that directly inspired Shor’s factoring algo rithm. The report further analyzes the algebraic structure of Simon’s algorithm through Gaussian elimination over GF(2), hidden XOR periodicity, and coset-state superpositions. In addition, the study examines advanced quantum phenomena including interaction-free measurement in the Elitzur–Vaidman bomb-testing protocol, quantum teleportation via entanglement, and the broader implications of complexity separations involving BQP, BPP, and PSPACE. By synthesizing classical probabilistic techniques with quantum query complexity, the report demonstrates how quantum computation transforms computational paradigms from local deterministic evaluation to global interference-driven information processing. These foun dational principles continue to guide modern developments in quantum algorithms, quantum cryptanalysis, and fault-tolerant quantum hardware within the Noisy Intermediate-Scale Quantum (NISQ) era.
Abstract In this chapter, we introduce the definitions of automata Turing machines. We present different flavors of Turing machines including deterministic, probabilistic, and multi-tape machines. We present several complexity classes, i.e. collections of problems that can be solved by a machine with similar resources, including the P and NP classes. We present the Church-Turing thesis, which states that if a problem can be solved by a physical machine, then it can also be solved by any deterministic Turing machine. In the last part of the chapter, we introduce quantum Turing machines and the quantum circuit model. We study the complexity class BQP. This is the class of problems that can be solved by a quantum computer with polynomial resources and a small error probability. Finally, we introduce QMA, the quantum version of the complexity class NP. We present the k-LOCAL problem, and we show that this problem is in QMA
Quantum Computing and Quantum Information Science seem very promising and developing rapidly since its inception in early 1980s by Paul Benioff with the proposal of quantum mechanical model of the Turing machine and later By Richard Feynman and Yuri Manin for the proposal of a quantum computers for simulating various problems that classical computer could not. Quantum computers have a computational advantage for some problems, over classical computers and most applications are trying to use an efficient combination of classical and quantum computers like Shor’s factoring algorithm. Other areas that are expected to be benefitted from quantum computing are Machine Learning and deep learning, molecular biology, genomics and cancer research, space exploration, atomic and nuclear research and macro-economic forecasting. This paper represents a brief overview of the state of art of quantum computing and quantum information science with discussions of various theoretical and experimental aspects adopted by the researchers.