The recent proliferation of NISQ devices has made it imperative to understand their power. In this work, we define and study the complexity class NISQ, which encapsulates problems that can be efficiently solved by a classical computer with access to noisy quantum circuits. We establish super-polynomial separations in the complexity among classical computation, NISQ, and fault-tolerant quantum computation to solve some problems based on modifications of Simon's problems. We then consider the power of NISQ for three well-studied problems. For unstructured search, we prove that NISQ cannot achieve a Grover-like quadratic speedup over classical computers. For the Bernstein-Vazirani problem, we show that NISQ only needs a number of queries logarithmic in what is required for classical computers. Finally, for a quantum state learning problem, we prove that NISQ is exponentially weaker than classical computers with access to noiseless constant-depth quantum circuits.
The recent proliferation of NISQ devices has made it imperative to understand their power. In this work, we define and study the complexity class NISQ, which encapsulates problems that can be efficiently solved by a classical computer with access to noisy quantum circuits. We establish super-polynomial separations in the complexity among classical computation, NISQ, and fault-tolerant quantum computation to solve some problems based on modifications of Simon's problems. We then consider the power of NISQ for three well-studied problems. For unstructured search, we prove that NISQ cannot achieve a Grover-like quadratic speedup over classical computers. For the Bernstein-Vazirani problem, we show that NISQ only needs a number of queries logarithmic in what is required for classical computers. Finally, for a quantum state learning problem, we prove that NISQ is exponentially weaker than classical computers with access to noiseless constant-depth quantum circuits.
Quantum computing has noteworthy speedup over classical computing by taking advantage of quantum parallelism, i.e., the superposition of states. In particular, quantum search is widely used in various computationally hard problems. Grover's search algorithm finds the target element in an unsorted database with quadratic speedup than classical search and has been proved to be optimal in terms of the number of queries to the database. The challenge, however, is that Grover's search algorithm leads to high numbers of quantum gates, which make it infeasible for the Noise-Intermediate-Scale-Quantum (NISQ) computers. In this paper, we propose a novel hardware efficient quantum search algorithm to overcome this challenge. Our key idea is to replace the global diffusion operation with low-cost local diffusions. Our analysis shows that our algorithm has similar oracle complexity to the original Grover's search algorithm while significantly reduces the circuit depth and gate count. The circuit cost reduction leads to a remarkable improvement in the system success rates, paving the way for quantum search on NISQ machines.
A universal fault-tolerant quantum computer that can solve efficiently problems such as integer factorization and unstructured database search requires millions of qubits with low error rates and long coherence times. While the experimental advancement towards realizing such devices will potentially take decades of research, noisy intermediate-scale quantum (NISQ) computers already exist. These computers are composed of hundreds of noisy qubits, i.e. qubits that are not error-corrected, and therefore perform imperfect operations in a limited coherence time. In the search for quantum advantage with these devices, algorithms have been proposed for applications in various disciplines spanning physics, machine learning, quantum chemistry and combinatorial optimization. The goal of such algorithms is to leverage the limited available resources to perform classically challenging tasks. In this review, we provide a thorough summary of NISQ computational paradigms and algorithms. We discuss the key structure of these algorithms, their limitations, and advantages. We additionally provide a comprehensive overview of various benchmarking and software tools useful for programming and testing NISQ devices.
<!--HTML-->A universal fault-tolerant quantum computer that can solve efficiently problems such as integer factorization and unstructured database search requires millions of qubits with low error rates and long coherence times. While the experimental advancement towards realizing such devices will potentially take decades of research, noisy intermediate-scale quantum (NISQ) computers already exist. These computers are composed of hundreds of noisy qubits, i.e. qubits that are not error-corrected, and therefore perform imperfect operations in a limited coherence time. In the search for quantum advantage with these devices, algorithms have been proposed for applications in various disciplines spanning physics, machine learning, quantum chemistry and combinatorial optimization. The goal of such algorithms is to leverage the limited available resources to perform classically challenging tasks. In this talk, I provide an overview of NISQ algorithms, their limitations and potential advantages.
Grover's algorithm stands as a cornerstone of quantum computing, offering a theoretical quadratic speedup for unstructured search problems. This allows for finding a target item in an unsorted database of N entries in approximately the square root of N steps, a significant improvement over classical algorithms which require a number of operations on the order of N in the worst case. This speedup becomes particularly compelling for very large datasets, where classical exhaustive search becomes computationally intractable. The algorithm achieves this by leveraging fundamental quantum mechanical principles, primarily superposition and interference. It operates by preparing qubits in a uniform superposition of all possible states, then iteratively applying a quantum oracle to mark the desired state by flipping its phase, followed by a diffusion operator that amplifies the probability of the marked state. Despite its theoretical promise, real-world implementation faces substantial challenges stemming from Noisy Intermediate-Scale Quantum (NISQ) hardware, which is characterized by high error rates and short coherence times. Consequently, achieving a true, scalable quantum advantage remains a future endeavor, contingent on significant hardware advancements. Nevertheless, Grover's algorithm holds significant potential across diverse fields, including enhancing brute-force attacks on cryptographic systems, accelerating solutions for optimization problems, and speeding up search processes in machine learning and unstructured database queries.
Abstract With powerful quantum computers already built1,2, we need more efficient quantum algorithms to achieve quantum supremacy over classical computers in the noisy intermediate-scale quantum (NISQ) era2,3. Grover's search algorithm4,5 and its generalization, quantum amplitude amplification6, provide quadratic speedup in solving many important scientific problems7. However, they still have exponential time complexity as the depths of their quantum circuits increase exponentially with the number of qubits6,7. To address this problem, we propose a new algorithm, Variational Quantum Search (VQS), which is based on the celebrated variational quantum algorithms8,9 and includes a parameterized quantum circuit, known as Ansatz. We show that a depth-10 Ansatz can amplify the total probability of k (k≥1) good elements, out of 2n elements represented by n+1 qubits, from k/2n to nearly 1, as verified for n up to 26, and that the maximum depth of quantum circuits in the VQS increases linearly with the number of qubits. We demonstrate that a depth-56 circuit in VQS can replace a depth-270,989 circuit in Grover's algorithm, and thus VQS is more suitable for NISQ computers. We envisage our VQS could exponentially speed up the solutions to many important problems, including the NP-complete problems, which is widely considered impossible.
Consider the model of computation where we start with two halves of a 2n-qubit maximally entangled state. We get to apply a universal quantum computation on one half, measure both halves at the end, and perform classical postprocessing. This model, which we call 21BQP, was defined in STOC 2017 [ABKM17] to capture the power of permutational computations on special input states. As observed in [ABKM17], this model can be viewed as a natural generalization of the one-clean-qubit model (DQC1) where we learn the content of a high entropy input state only after the computation is completed. An interesting open question is to characterize the power of this model, which seems to sit nontrivially between DQC1 and BQP. In this paper, we show that despite its limitations, this model can carry out many well-known quantum computations that are candidates for exponential speed-up over classical computations (and possibly DQC1). In particular, 21BQP can simulate Instantaneous Quantum Polynomial Time (IQP) and solve the Deutsch-Jozsa problem, Bernstein-Vazirani problem, Simon's problem, and period finding. As a consequence, 21BQP also solves Order Finding and Factoring outside of the oracle setting. Furthermore, 21BQP can solve Forrelation and the corresponding oracle problem given by Raz and Tal [RT22] to separate BQP and PH. We also study limitations of 21BQP and show that similarly to DQC1, 21BQP cannot distinguish between unitaries which are close in trace distance, then give an oracle separating 21BQP and BQP. Due to this limitation, 21BQP cannot obtain the quadratic speedup for unstructured search given by Grover's algorithm [Gro96]. We conjecture that 21BQP cannot solve 3-Forrelation.