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 series on nonlinear science, series A

Limits and Solvability of Quantum Computing

Published Nov 25, 2024• 0 citations
Publisher

Abstract

The extent to which the possibilities and limits of computability depend on the assumed mathematical formalism is particularly evident in quantum computing. Here, methods, algorithms, and basic concepts of classical digital computing must be translated into the mathematical formalism of quantum mechanics and new concepts of quantum formalism must be utilized in order to overcome the classical limits of computability. In the sense of Church’s thesis, a classical digital computer can also be understood as a circuit of Boolean gates that process bits. In quantum computing, they are replaced by quantum gates that represent the unitary operators of quantum mechanics and process quantum bits. The enormous computing advantages are due to the special features of quantum mechanical states such as superposition and entanglement. The calculation results of a quantum computer are explained by the quantum mechanical measurement process. Classical calculation methods such as fast Fourier transformations are translated into quantum formalism and thus enable the solution of difficult calculation problems in polynomial time (e.g., factorization with the Shor algorithm). However, in this case, it cannot be ruled out that there is also a classical digital solution in polynomial time. This distinguishes the result from the fundamental impossibility of a digital solution, which was shown for real computing in Chapter 7. Classical pattern recognition and classification of machine learning (ML) with neural networks can also be translated into quantum formalism and lead to a considerable increase in performance with superposition and entanglement. In quantum complexity theory, previous NP problems can be traced back to P problems. In quantum computing too, the theoretical possibilities and limits depend on the mathematical formalism assumed. The technical– physical realization of a quantum computer, on the contrary, is again an empirical question.

DOI
10.1142/9789811290084_0010

Related papers

Quantum supremacy: some fundamental concepts

Man‐Hong Yung

Quantum computation was envisioned by Feynman as a valuable means of solving quantum problems [1]. The question is, how do we prove the superiority of quantum computing over classical devices? A common misconception in describing the power of a quantum computer over a classical computer is that quantum bits can be prepared in a superposition of an exponential number of states, which cannot be achieved with classical bits. This statement is certainly true, but it does not tell us, specifically, what problems quantum computers can efficiently solve while classical computers fail to do so. In fact, based exactly on the technique of Feynman's path integral, the output (i.e. transition amplitude) of any quantum circuit can be calculated classically with a polynomial amount of memory (although the temporal cost would be exponential). Therefore any quantum computation can be simulated classically; the key question is about the efficiency. Much effort has been made trying to pin down the power of quantum computers based on the machinery of the computational complexity theory. In particular, the class of computational (decision) problems that can be solved efficiently by a quantum computer is called BQP (bounded-error quantum polynomial time); the counterpart for classical computers is called P (polynomial time). Of course, BQP cannot be less than P; in principle quantum computers can simulate classical computers efficiently. The point is that the foundation of quantum computation cannot be established without a proof showing that BQP is strictly larger than P (i.e. BQP ≠ P). In this sense, this question is as interesting as the famous challenge of proving P ≠ NP (non-deterministic polynomial time). A well known instance of an NP problem is the factoring problem; Shor's quantum algorithm is capable of solving the factoring problem in polynomial time, which is not achievable with the best classical algorithm discovered so far. However, we still cannot rigorously exclude the possibility of the existence of an efficient classical algorithm for factoring. Although again without a proof, it is commonly believed that quantum computers are unable to solve some of the NP problems. In fact, the proof of this statement (if true) provides a possible path to prove P ≠ NP. A potentially less demanding question would be, when do we expect a quantum computer to be able to perform some well defined tasks (not necessarily related to any practical problem) that cannot be simulated with any currently available classical device, within a reasonable time? Once achieved, the status is called ‘quantum supremacy' [2]. One may ask, what about Grover's search algorithm, which provides a quadratic speedup over the classical search? Can we say that we can already achieve quantum supremacy with Grover's algorithm? The problem is that, instead of taking the large-N limit, quantum supremacy requires us to determine the actual number of qubits and gates that can no longer be simulated by classical computers within a reasonable time. To elaborate further, we remark that there can be two notions of classical simulation, namely ‘strong simulation' versus ‘weak simulation'. Strong simulation refers to the cases of calculating the transition probabilities, or expectation values of observables, to a high accuracy in polynomial time. Weak simulation requires the probability distributions to be accurately reproduced, which involves ‘sampling' the different outcomes of the quantum devices. Some quantum circuits that cannot be strongly simulated with an efficient classical means may have efficient classical methods for weak simulation [3]. However, we should be careful about the accuracy requirement in the simulation tasks. For example, for many decision problems, it may be sufficient to determine the transition amplitudes to within an additive error, instead of multiplicative error. In other words, the classical simulability of quantum computational problems depends on the accuracy requirement. Currently, there are three popular approaches for achieving quantum supremacy (see Fig. 1), namely (i) boson sampling [4], (ii) sampling IQP (instantaneous quantum polynomial) circuits [5], and (iii) sampling chaotic quantum circuits [6]. In all of these approaches, distributions of different bit strings or photon numbers are sampled from the quantum devices. Furthermore, they all involve the assumption that classical computers are unable to efficiently determine the transition amplitudes, and/or reproduce (or approximate) the distributions of quantum devices performing these tasks, in the sense of both strong and weak simulations. Three different approaches for achieving quantum supremacy: (a) boson sampling; (b) IQP circuits; (c) chaotic quantum circuits. In boson sampling, single photons are injected into different modes of a linear optical network. The task is to determine the photon distributions at the output ports. The key feature of boson sampling is that the transition amplitudes are related to the permanents of complex matrices, which are in general very difficult to calculate exactly, or approximate to within an multiplicative error; these problems belong to the #P-hard complexity class. Moreover, efficient weak simulation of boson sampling is believed to be impossible, unless the polynomial hierarchy collapses to its third level. However, a recent numerical study suggests that, in order to achieve quantum supremacy with boson sampling, one needs to simultaneously generate at least 50 or more single photons, which is still highly technologically challenging. An interesting question is whether linear optics, in the setting of boson sampling, can be applied to solve decision problems. In this case, the transition amplitudes may need to be determined to an additive error. However, we found that a large class of decision problems associated with boson sampling can be simulated by a classical computer [7], settling an open problem [8] by Aaronson and Hance. IQP circuits represent a simplified quantum-circuit model. The initial state starts from the all-zero state, |000…0〉, followed by applying Hadamard gates to each qubit. Then, diagonal gates are applied to the qubits, followed by applying Hadamard gates to each qubit again. The argument of showing the complexity in simulating IQP circuits is similar to that of boson sampling. In fact, the complexity of boson sampling was inspired by the complexity results of IQP circuits. However, when subject to noise, IQP circuits may become classically simulable [9]. Lastly, chaotic quantum circuits refer to the class of quantum circuits where two-qubit gates are applied regularly, while single-qubit gates are applied randomly from a gate set. The output distributions of these circuits approach the so-called Porter–Thomas distribution, which is a characteristic feature of quantum chaos. Recently, there have been several numerical investigations aiming to explore the ultimate limit of classical computing in simulating low-depth quantum circuits. For the ideal cases, one needs to consider both the qubit number and circuit depth for benchmarking quantum supremacy. However, in the presence of noise, these chaotic circuits may also become classically simulable for high-depth circuits [10]. Finally, other than these three approaches, one should expect that quantum supremacy can be achieved for many practical applications, e.g. simulation of quantum chemistry or quantum machine learning. When will it happen? Only time will tell!

National Science Review•Jul 4, 2018•24 citations

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

Quantum computing

Guolin Wu

Quantum computing operates by manipulating the quantum state of a system to solve problems intractable for classical computing. These problems, previously considered limitations of classical algorithms, have solutions through quantum approaches. Therefore, quantum computing suggests that the complexity of such problems lies in the current epistemic state rather than the objective state of the problem. Computational complexity can be classified into objective and epistemic complexity. Some classical problems exhibiting exponential complexity fall into the epistemic category, as their solutions depend on the current state of human knowledge and available tools. Quantum computing suggests that even mathematics isn’t entirely objective, and mathematics, in one sense, is human-made and a kind of technology, which reflects our intention and planning. Computational complexity, therefore, bridges the objective and subjective. Overcoming classical complexity necessitates advancements in scientific theories, algorithms, and quantum technology, all of which rely on the development of human cognitive abilities. Quantum computing is not just a mathematical construct, but also has physical meaning. If it were purely mathematical, classical physics and systems could potentially achieve the same results. What makes the quantum world special is its empirical nature—the physical reality of quantum chips, quantum algorithms, and quantum evolution. Quantum supremacy, or quantum advantage, refers to the potential superiority of quantum computers over classical ones. Controllable quantum systems offer an overwhelming advantage in terms of manipulation and dominance compared to classical systems. Essentially, quantum computing has the potential to significantly outperform classical computing. Many experts, including Shor, have proposed that quantum computing’s power stems from its ability to perform multiple computations simultaneously—a concept often referred to as the Quantum parallelism thesis. Rather, some argue that the true source of quantum computing acceleration lies in the fundamental differences between classical and quantum logic. However, it’s important to note that quantum logic, while providing a new perspective, does not directly address the core principle of quantum parallelism. This dominance stems from quantum physics’ unique properties: Exponential storage capacity, parallel computing inherent to its nature (ontological), and the ability to perform calculations with exponential speedup through quantum algorithms.

Routledge eBooks•Oct 8, 2025•0 citations

Introduction to Special Section on Quantum Computation

Umesh V. Vazirani

The rapid evolution of computers in the half century since their invention has resulted in dramatically smaller and faster computers. However, from a computational point of view, all these computers look alike; for example, they are built out of simple logic gates. A fundamental thesis of computer science---the modern form of the Church--Turing thesis---asserts that this is inevitable in a deep sense. Any computer can be simulated with at most a polynomial factor slowdown by a probabilistic Turing machine. Quantum computation poses the first credible challenge to this thesis. It goes back to a suggestion by Feynman [4], who pointed out that there appears to be no efficient way of simulating a quantum mechanical system on a computer, and suggested that, perhaps, a computer based on quantum physical principles might be able to carry out the simulation efficiently. Two formal models for quantum computers---the quantum Turing machine [2] and quantum computational networks [3]---were defined by Deutsch. The first three papers in this issue describe efficient quantum algorithms for computational tasks that we do not know how to solve classically. In "Quantum Complexity Theory," Bernstein and Vazirani give the first formal evidence that quantum computers violate the modern form of the Church--Turing thesis. They show that a certain problem---the recursive Fourier sampling problem---can be solved in polynomial time on a quantum Turing machine, but relative to an oracle, requires superpolynomial time on a classical probabilistic Turing machine. Simon, in the paper "On the Power of Quantum Computation" introduces a fundamental projection technique and uses it to design an efficient quantum algorithm to determine whether a certain type of function is 2-1 or 1-1. He further shows that, relative to an oracle, this problem requires exponential time on a classical probabilistic Turing machine. In the paper "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer," Shor gives remarkable polynomial time quantum algorithms for two of the most famous problems in computer science: factoring and discrete log. Since the computational hardness of these problems is the basis of several famous cryptosystems, Shor's paper very dramatically underlines the power of quantum computers. To understand the computational power of quantum computers, it is helpful to consider a quantum mechanical system of n particles, each of which can be in one of two states, labeled $|0\rangle$ and $|1\rangle$. If this were a classical system, then its instantaneous state could be described by n bits. However, in quantum physics, the system is allowed to be in a linear superposition of configurations, and indeed the instantaneous state of the system is described by a unit vector in the 2n dimensional vector space, whose basis vectors correspond to all the2n classical configurations. Therefore, to describe the instantaneous state of the system, we must specify 2n complex numbers. Nature must update 2n complex numbers at each instant to evolve the system in time. This is an extraordinary amount of effort, since even for n = 200, 2n is larger than estimates of the number of elementary particles in the visible universe. Nonetheless, there are limits to the power of quantum computers. In "Strengths and Weaknesses of Quantum Computing," Bennett, Bernstein, Brassard, and Vazirani show that, relative to a random oracle, with probability 1, the class NP cannot be solved on a quantum Turing machine in time o(2n/2). This bound is tight, since recent work of Grover [5] has shown how to accept any language in NP in time O(2n/2) on a quantum Turing machine. Quantum computers are necessarily time reversible. Indeed, Bennett's work [1] on reversible computation inspired early work on quantum computation that preceded Feynman's paper [4]. The reversibility requirement makes it quite complex to implement even basic computational primitives such as looping or composition. In "Quantum Complexity Theory," Bernstein and Vazirani show how to implement quantum programming primitives and give a construction for an efficient universal quantum Turing machine. The structure of the universal quantum Turing machine is quite simple: it consists of a deterministic Turing machine with a single "quantum coin flip." In "Quantum Computability," Adleman, DeMarrais, and Huang greatly simplify this further by showing that a very simple type of coin flip is sufficient---a rotation by an angle $\theta$ such that ${\rm sin} \theta = 3/5$. Making quantum computers robust against noise and decoherence is an important and challenging problem. In "Stabilization of Quantum Computations by Symmetrization," Barenco, Berthiaume, Deutsch, Ekert, Jozsa, and Macchiavello show how to use the quantum watchdog effect to stabilize a quantum computation against noise. Their method is based on running several copies of the quantum computer in parallel and projecting its state into the symmetric subspace at frequent intervals. They show that the quantum watchdog effect results in the suppression of errors that lie outside the symmetric subspace. Quantum computation touches upon the foundations of both computer science and quantum physics. It is not unlikely that the issues raised by quantum computation will stimulate further research into the foundations of quantum physics. I wish to express my gratitude to several people who made this special section possible. Oded Goldreich acted as editor for two of the papers in the issue and dealt with them with his characteristic efficiency and judgment. The editorial staff at SIAM, most notably Lisa Dougherty, Beth Gallagher, Deidre Wunderlich, and Sam Young, were extremely helpful, patient, and resourceful. Finally, I would like to thank a number of referees whose careful and timely reviews were critical to putting together this issue. Umesh Vazirani

SIAM Journal on Computing•Oct 1, 1997•4 citations

Fundamentals of Quantum Machines

Soham S. Bhoir, Harshal H. Dave, Devi Priya Rangasamy

Quantum machines, grounded in the principles of quantum mechanics, harness the extraordinary computational power derived from quantum bits (qubits), contrasting with classical machines reliant on classical bits. Qubits, distinguished by properties like superposition and entanglement, empower quantum algorithms to solve intricate problems with exponential speedup. Quantum states, fundamental to quantum mechanics, serve as descriptors for quantum systems, laying the foundation for subsequent calculations. Quantum gates, unitary operators manipulating qubits, are pivotal in quantum computing, extending beyond single-particle systems to encompass multi-particle scenarios. This flexibility finds applications in quantum simulation, optimization, cryptography, machine learning, and more. Quantum computing’s potential to revolutionize fields arises from its ability to tackle computationally intractable problems. Applications span quantum simulation, optimization, cryptography, machine learning, chemistry, materials science, financial modeling, and transportation. quantum protocols, including communication and cryptography, leverage unique quantum properties. Prominent quantum algorithms, such as Deutsch-Jozsa, Bernstein-Vazirani, Grover’s, and Shor’s, exploit qubit features for efficient problem-solving. These algorithms harness superposition and entanglement, allowing parallel calculations across multiple possibilities. In the landscape of quantum computing, the interplay of quantum bits, gates, states, and algorithms showcases the potential for transformative advances in computation.

Chapman & Hall/CRC eBooks•Oct 1, 2024•1 citation

An overview on quantum computing for technology

Vijay Kumar, S. Gupta, Fateh Singh Gill

Quantum computing is a potential technological revolution that will transform the entire field of information processing. However, quantum computing like classical bits in classical computers is operated using quantum bits principle physics based on quantum mechanics. Quantum computing explores many solution spaces simultaneously because of a fundamental difference from the classical computation paradigms, leading to the possibility of exponential speed-up on some computational plant tasks. This paper discusses quantum computing with essential concepts like quantum superposition, entanglement, and applications such as cryptography, optimization, and drug discovery and machine learning. Quantum computing will enable numerous groundbreaking discoveries that were previously unattainable and will bequeath a lasting legacy in the digital innovation era. Quantum computing is an information processing technique that harnesses the laws of quantum mechanics to conduct calculations far faster circumvented by traditional digital computers. Digital computers utilize bits, which may take one of two forms: 0 or 1. This superposition of quantum superposition and entanglement yielded qubits unique qualities that can’t be expected in classical systems. Indeed, superposition enables qubits to take numerous forms simultaneously, while entanglement enables qubits to be connected such their properties are connected. In cryptography, quantum computers can decrypt existing cryptographic keys or develop new, more secure quantum encryption using qubits. Quantum computers can dramatically accelerate materials science and drug design by allowing scientists to simulate how molecules interact more accurately. In conclusion, quantum computing represents a unique information processing change and has a future impact on science, technology, and society.

CRC Press eBooks•Nov 19, 2024•5 citations
The extent to which the possibilities and limits of computability depend on the assumed mathematical formalism is particularly evident in quantum computing. Here, methods, algorithms, and basic concepts of classical digital computing must be translated into the mathematical formalism of quantum mechanics and new concepts of quantum formalism must be utilized in order to overcome the classical limits of computability. In the sense of Church’s thesis, a classical digital computer can also be understood as a circuit of Boolean gates that process bits. In quantum computing, they are replaced by quantum gates that represent the unitary operators of quantum mechanics and process quantum bits. The enormous computing advantages are due to the special features of quantum mechanical states such as superposition and entanglement. The calculation results of a quantum computer are explained by the quantum mechanical measurement process. Classical calculation methods such as fast Fourier transformations are translated into quantum formalism and thus enable the solution of difficult calculation problems in polynomial time (e.g., factorization with the Shor algorithm). However, in this case, it cannot be ruled out that there is also a classical digital solution in polynomial time. This distinguishes the result from the fundamental impossibility of a digital solution, which was shown for real computing in Chapter 7. Classical pattern recognition and classification of machine learning (ML) with neural networks can also be translated into quantum formalism and lead to a considerable increase in performance with superposition and entanglement. In quantum complexity theory, previous NP problems can be traced back to P problems. In quantum computing too, the theoretical possibilities and limits depend on the mathematical formalism assumed. The technical– physical realization of a quantum computer, on the contrary, is again an empirical question.
Quantum computation was envisioned by Feynman as a valuable means of solving quantum problems [1]. The question is, how do we prove the superiority of quantum computing over classical devices? A common misconception in describing the power of a quantum computer over a classical computer is that quantum bits can be prepared in a superposition of an exponential number of states, which cannot be achieved with classical bits. This statement is certainly true, but it does not tell us, specifically, what problems quantum computers can efficiently solve while classical computers fail to do so. In fact, based exactly on the technique of Feynman's path integral, the output (i.e. transition amplitude) of any quantum circuit can be calculated classically with a polynomial amount of memory (although the temporal cost would be exponential). Therefore any quantum computation can be simulated classically; the key question is about the efficiency. Much effort has been made trying to pin down the power of quantum computers based on the machinery of the computational complexity theory. In particular, the class of computational (decision) problems that can be solved efficiently by a quantum computer is called BQP (bounded-error quantum polynomial time); the counterpart for classical computers is called P (polynomial time). Of course, BQP cannot be less than P; in principle quantum computers can simulate classical computers efficiently. The point is that the foundation of quantum computation cannot be established without a proof showing that BQP is strictly larger than P (i.e. BQP ≠ P). In this sense, this question is as interesting as the famous challenge of proving P ≠ NP (non-deterministic polynomial time). A well known instance of an NP problem is the factoring problem; Shor's quantum algorithm is capable of solving the factoring problem in polynomial time, which is not achievable with the best classical algorithm discovered so far. However, we still cannot rigorously exclude the possibility of the existence of an efficient classical algorithm for factoring. Although again without a proof, it is commonly believed that quantum computers are unable to solve some of the NP problems. In fact, the proof of this statement (if true) provides a possible path to prove P ≠ NP. A potentially less demanding question would be, when do we expect a quantum computer to be able to perform some well defined tasks (not necessarily related to any practical problem) that cannot be simulated with any currently available classical device, within a reasonable time? Once achieved, the status is called ‘quantum supremacy' [2]. One may ask, what about Grover's search algorithm, which provides a quadratic speedup over the classical search? Can we say that we can already achieve quantum supremacy with Grover's algorithm? The problem is that, instead of taking the large-N limit, quantum supremacy requires us to determine the actual number of qubits and gates that can no longer be simulated by classical computers within a reasonable time. To elaborate further, we remark that there can be two notions of classical simulation, namely ‘strong simulation' versus ‘weak simulation'. Strong simulation refers to the cases of calculating the transition probabilities, or expectation values of observables, to a high accuracy in polynomial time. Weak simulation requires the probability distributions to be accurately reproduced, which involves ‘sampling' the different outcomes of the quantum devices. Some quantum circuits that cannot be strongly simulated with an efficient classical means may have efficient classical methods for weak simulation [3]. However, we should be careful about the accuracy requirement in the simulation tasks. For example, for many decision problems, it may be sufficient to determine the transition amplitudes to within an additive error, instead of multiplicative error. In other words, the classical simulability of quantum computational problems depends on the accuracy requirement. Currently, there are three popular approaches for achieving quantum supremacy (see Fig. 1), namely (i) boson sampling [4], (ii) sampling IQP (instantaneous quantum polynomial) circuits [5], and (iii) sampling chaotic quantum circuits [6]. In all of these approaches, distributions of different bit strings or photon numbers are sampled from the quantum devices. Furthermore, they all involve the assumption that classical computers are unable to efficiently determine the transition amplitudes, and/or reproduce (or approximate) the distributions of quantum devices performing these tasks, in the sense of both strong and weak simulations. Three different approaches for achieving quantum supremacy: (a) boson sampling; (b) IQP circuits; (c) chaotic quantum circuits. In boson sampling, single photons are injected into different modes of a linear optical network. The task is to determine the photon distributions at the output ports. The key feature of boson sampling is that the transition amplitudes are related to the permanents of complex matrices, which are in general very difficult to calculate exactly, or approximate to within an multiplicative error; these problems belong to the #P-hard complexity class. Moreover, efficient weak simulation of boson sampling is believed to be impossible, unless the polynomial hierarchy collapses to its third level. However, a recent numerical study suggests that, in order to achieve quantum supremacy with boson sampling, one needs to simultaneously generate at least 50 or more single photons, which is still highly technologically challenging. An interesting question is whether linear optics, in the setting of boson sampling, can be applied to solve decision problems. In this case, the transition amplitudes may need to be determined to an additive error. However, we found that a large class of decision problems associated with boson sampling can be simulated by a classical computer [7], settling an open problem [8] by Aaronson and Hance. IQP circuits represent a simplified quantum-circuit model. The initial state starts from the all-zero state, |000…0〉, followed by applying Hadamard gates to each qubit. Then, diagonal gates are applied to the qubits, followed by applying Hadamard gates to each qubit again. The argument of showing the complexity in simulating IQP circuits is similar to that of boson sampling. In fact, the complexity of boson sampling was inspired by the complexity results of IQP circuits. However, when subject to noise, IQP circuits may become classically simulable [9]. Lastly, chaotic quantum circuits refer to the class of quantum circuits where two-qubit gates are applied regularly, while single-qubit gates are applied randomly from a gate set. The output distributions of these circuits approach the so-called Porter–Thomas distribution, which is a characteristic feature of quantum chaos. Recently, there have been several numerical investigations aiming to explore the ultimate limit of classical computing in simulating low-depth quantum circuits. For the ideal cases, one needs to consider both the qubit number and circuit depth for benchmarking quantum supremacy. However, in the presence of noise, these chaotic circuits may also become classically simulable for high-depth circuits [10]. Finally, other than these three approaches, one should expect that quantum supremacy can be achieved for many practical applications, e.g. simulation of quantum chemistry or quantum machine learning. When will it happen? Only time will tell!
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.
Quantum computing operates by manipulating the quantum state of a system to solve problems intractable for classical computing. These problems, previously considered limitations of classical algorithms, have solutions through quantum approaches. Therefore, quantum computing suggests that the complexity of such problems lies in the current epistemic state rather than the objective state of the problem. Computational complexity can be classified into objective and epistemic complexity. Some classical problems exhibiting exponential complexity fall into the epistemic category, as their solutions depend on the current state of human knowledge and available tools. Quantum computing suggests that even mathematics isn’t entirely objective, and mathematics, in one sense, is human-made and a kind of technology, which reflects our intention and planning. Computational complexity, therefore, bridges the objective and subjective. Overcoming classical complexity necessitates advancements in scientific theories, algorithms, and quantum technology, all of which rely on the development of human cognitive abilities. Quantum computing is not just a mathematical construct, but also has physical meaning. If it were purely mathematical, classical physics and systems could potentially achieve the same results. What makes the quantum world special is its empirical nature—the physical reality of quantum chips, quantum algorithms, and quantum evolution. Quantum supremacy, or quantum advantage, refers to the potential superiority of quantum computers over classical ones. Controllable quantum systems offer an overwhelming advantage in terms of manipulation and dominance compared to classical systems. Essentially, quantum computing has the potential to significantly outperform classical computing. Many experts, including Shor, have proposed that quantum computing’s power stems from its ability to perform multiple computations simultaneously—a concept often referred to as the Quantum parallelism thesis. Rather, some argue that the true source of quantum computing acceleration lies in the fundamental differences between classical and quantum logic. However, it’s important to note that quantum logic, while providing a new perspective, does not directly address the core principle of quantum parallelism. This dominance stems from quantum physics’ unique properties: Exponential storage capacity, parallel computing inherent to its nature (ontological), and the ability to perform calculations with exponential speedup through quantum algorithms.
The rapid evolution of computers in the half century since their invention has resulted in dramatically smaller and faster computers. However, from a computational point of view, all these computers look alike; for example, they are built out of simple logic gates. A fundamental thesis of computer science---the modern form of the Church--Turing thesis---asserts that this is inevitable in a deep sense. Any computer can be simulated with at most a polynomial factor slowdown by a probabilistic Turing machine. Quantum computation poses the first credible challenge to this thesis. It goes back to a suggestion by Feynman [4], who pointed out that there appears to be no efficient way of simulating a quantum mechanical system on a computer, and suggested that, perhaps, a computer based on quantum physical principles might be able to carry out the simulation efficiently. Two formal models for quantum computers---the quantum Turing machine [2] and quantum computational networks [3]---were defined by Deutsch. The first three papers in this issue describe efficient quantum algorithms for computational tasks that we do not know how to solve classically. In "Quantum Complexity Theory," Bernstein and Vazirani give the first formal evidence that quantum computers violate the modern form of the Church--Turing thesis. They show that a certain problem---the recursive Fourier sampling problem---can be solved in polynomial time on a quantum Turing machine, but relative to an oracle, requires superpolynomial time on a classical probabilistic Turing machine. Simon, in the paper "On the Power of Quantum Computation" introduces a fundamental projection technique and uses it to design an efficient quantum algorithm to determine whether a certain type of function is 2-1 or 1-1. He further shows that, relative to an oracle, this problem requires exponential time on a classical probabilistic Turing machine. In the paper "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer," Shor gives remarkable polynomial time quantum algorithms for two of the most famous problems in computer science: factoring and discrete log. Since the computational hardness of these problems is the basis of several famous cryptosystems, Shor's paper very dramatically underlines the power of quantum computers. To understand the computational power of quantum computers, it is helpful to consider a quantum mechanical system of n particles, each of which can be in one of two states, labeled ∣0⟩|0\rangle∣0⟩ and ∣1⟩|1\rangle∣1⟩. If this were a classical system, then its instantaneous state could be described by n bits. However, in quantum physics, the system is allowed to be in a linear superposition of configurations, and indeed the instantaneous state of the system is described by a unit vector in the 2n dimensional vector space, whose basis vectors correspond to all the2n classical configurations. Therefore, to describe the instantaneous state of the system, we must specify 2n complex numbers. Nature must update 2n complex numbers at each instant to evolve the system in time. This is an extraordinary amount of effort, since even for n = 200, 2n is larger than estimates of the number of elementary particles in the visible universe. Nonetheless, there are limits to the power of quantum computers. In "Strengths and Weaknesses of Quantum Computing," Bennett, Bernstein, Brassard, and Vazirani show that, relative to a random oracle, with probability 1, the class NP cannot be solved on a quantum Turing machine in time o(2n/2). This bound is tight, since recent work of Grover [5] has shown how to accept any language in NP in time O(2n/2) on a quantum Turing machine. Quantum computers are necessarily time reversible. Indeed, Bennett's work [1] on reversible computation inspired early work on quantum computation that preceded Feynman's paper [4]. The reversibility requirement makes it quite complex to implement even basic computational primitives such as looping or composition. In "Quantum Complexity Theory," Bernstein and Vazirani show how to implement quantum programming primitives and give a construction for an efficient universal quantum Turing machine. The structure of the universal quantum Turing machine is quite simple: it consists of a deterministic Turing machine with a single "quantum coin flip." In "Quantum Computability," Adleman, DeMarrais, and Huang greatly simplify this further by showing that a very simple type of coin flip is sufficient---a rotation by an angle θ\thetaθ such that sinθ=3/5{\rm sin} \theta = 3/5sinθ=3/5. Making quantum computers robust against noise and decoherence is an important and challenging problem. In "Stabilization of Quantum Computations by Symmetrization," Barenco, Berthiaume, Deutsch, Ekert, Jozsa, and Macchiavello show how to use the quantum watchdog effect to stabilize a quantum computation against noise. Their method is based on running several copies of the quantum computer in parallel and projecting its state into the symmetric subspace at frequent intervals. They show that the quantum watchdog effect results in the suppression of errors that lie outside the symmetric subspace. Quantum computation touches upon the foundations of both computer science and quantum physics. It is not unlikely that the issues raised by quantum computation will stimulate further research into the foundations of quantum physics. I wish to express my gratitude to several people who made this special section possible. Oded Goldreich acted as editor for two of the papers in the issue and dealt with them with his characteristic efficiency and judgment. The editorial staff at SIAM, most notably Lisa Dougherty, Beth Gallagher, Deidre Wunderlich, and Sam Young, were extremely helpful, patient, and resourceful. Finally, I would like to thank a number of referees whose careful and timely reviews were critical to putting together this issue. Umesh Vazirani
Quantum machines, grounded in the principles of quantum mechanics, harness the extraordinary computational power derived from quantum bits (qubits), contrasting with classical machines reliant on classical bits. Qubits, distinguished by properties like superposition and entanglement, empower quantum algorithms to solve intricate problems with exponential speedup. Quantum states, fundamental to quantum mechanics, serve as descriptors for quantum systems, laying the foundation for subsequent calculations. Quantum gates, unitary operators manipulating qubits, are pivotal in quantum computing, extending beyond single-particle systems to encompass multi-particle scenarios. This flexibility finds applications in quantum simulation, optimization, cryptography, machine learning, and more. Quantum computing’s potential to revolutionize fields arises from its ability to tackle computationally intractable problems. Applications span quantum simulation, optimization, cryptography, machine learning, chemistry, materials science, financial modeling, and transportation. quantum protocols, including communication and cryptography, leverage unique quantum properties. Prominent quantum algorithms, such as Deutsch-Jozsa, Bernstein-Vazirani, Grover’s, and Shor’s, exploit qubit features for efficient problem-solving. These algorithms harness superposition and entanglement, allowing parallel calculations across multiple possibilities. In the landscape of quantum computing, the interplay of quantum bits, gates, states, and algorithms showcases the potential for transformative advances in computation.
Quantum computing is a potential technological revolution that will transform the entire field of information processing. However, quantum computing like classical bits in classical computers is operated using quantum bits principle physics based on quantum mechanics. Quantum computing explores many solution spaces simultaneously because of a fundamental difference from the classical computation paradigms, leading to the possibility of exponential speed-up on some computational plant tasks. This paper discusses quantum computing with essential concepts like quantum superposition, entanglement, and applications such as cryptography, optimization, and drug discovery and machine learning. Quantum computing will enable numerous groundbreaking discoveries that were previously unattainable and will bequeath a lasting legacy in the digital innovation era. Quantum computing is an information processing technique that harnesses the laws of quantum mechanics to conduct calculations far faster circumvented by traditional digital computers. Digital computers utilize bits, which may take one of two forms: 0 or 1. This superposition of quantum superposition and entanglement yielded qubits unique qualities that can’t be expected in classical systems. Indeed, superposition enables qubits to take numerous forms simultaneously, while entanglement enables qubits to be connected such their properties are connected. In cryptography, quantum computers can decrypt existing cryptographic keys or develop new, more secure quantum encryption using qubits. Quantum computers can dramatically accelerate materials science and drug design by allowing scientists to simulate how molecules interact more accurately. In conclusion, quantum computing represents a unique information processing change and has a future impact on science, technology, and society.