A universal fault-tolerant quantum computer that can efficiently solve 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 toward 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 within a limited coherence time. In the search for achieving quantum advantage with these devices, algorithms have been proposed for applications in various disciplines spanning physics, machine learning, quantum chemistry, and combinatorial optimization. The overarching goal of such algorithms is to leverage the limited available resources to perform classically challenging tasks. In this review, a thorough summary of NISQ computational paradigms and algorithms is provided. The key structure of these algorithms and their limitations and advantages are discussed. A comprehensive overview of various benchmarking and software tools useful for programming and testing NISQ devices is additionally provided.

Quantum simulation can help us study poorly understood topics such as high-temperature superconductivity and drug design. However, existing quantum simulation algorithms for current quantum computers often have drawbacks that impede their application. Here, we provide a hybrid quantum-classical algorithm for simulating the dynamics of quantum systems. Our approach takes the ansatz wave function as a linear combination of quantum states. The quantum states are fixed, and the combination parameters are variationally adjusted. Unlike existing variational quantum simulation algorithms, our algorithm does not require any classical-quantum feedback loop and by construction bypasses the barren plateau problem. Moreover, our algorithm does not require any complicated measurements such as the Hadamard test. The entire framework is compatible with existing experimental capabilities and thus can be implemented immediately.

The task of estimating the ground state of Hamiltonians is an important problem in physics with numerous applications ranging from solid-state physics to combinatorial optimization. We provide a hybrid quantum-classical algorithm for approximating the ground state of a Hamiltonian that builds on the powerful Krylov subspace method in a way that is suitable for current quantum computers. Our algorithm systematically constructs the ansatz by using any given choice of the initial state and the unitaries describing the Hamiltonian. The only task of the quantum computer is to measure overlaps and no feedback loops are required. The measurements can be performed efficiently on current quantum hardware without requiring any complicated measurements such as the Hadamard test. Finally, a classical computer solves a well-characterized quadratically constrained optimization program. Our algorithm can reuse previous measurements to calculate the ground state of a wide range of Hamiltonians without requiring additional quantum resources. Further, we demonstrate our algorithm for solving a class of problems with thousands of qubits. The algorithm works for almost every random choice of the initial state and circumvents the barren plateau problem.

The goal of machine learning is to facilitate a computer to execute a specific task without explicit instruction by an external party. Quantum foundations seek to explain the conceptual and mathematical edifice of quantum theory. Recently, ideas from machine learning have successfully been applied to different problems in quantum foundations. Here, the authors compile the representative works done so far at the interface of machine learning and quantum foundations. The authors conclude the survey with potential future directions.

We provide a noisy intermediate-scale quantum framework for simulating the dynamics of open quantum systems, generalized time evolution, non-linear differential equations and Gibbs state preparation. Our algorithm does not require any classical–quantum feedback loop, bypass the barren plateau problem and does not necessitate any complicated measurements such as the Hadamard test. We introduce the notion of the hybrid density matrix, which allows us to disentangle the different steps of our algorithm and delegate classically demanding tasks to the quantum computer. Our algorithm proceeds in three disjoint steps. First, we select the ansatz, followed by measuring overlap matrices on a quantum computer. The final step involves classical post-processing data from the second step. Our algorithm has potential applications in solving the Navier–Stokes equation, plasma hydrodynamics, quantum Boltzmann training, quantum signal processing and linear systems. Our entire framework is compatible with current experiments and can be implemented immediately.

Pseudorandom quantum states (PRSs) and pseudorandom unitaries (PRUs) possess the dual nature of being efficiently constructible while appearing completely random to any efficient quantum algorithm. In this study, we establish fundamental bounds on pseudorandomness. We show that PRSs and PRUs exist only when the probability that an error occurs is negligible, ruling out their generation on noisy intermediate-scale and early fault-tolerant quantum computers. Further, we show that PRUs need imaginarity while PRS do not have this restriction. This implies that quantum randomness requires in general a complex-valued formalism of quantum mechanics, while for random quantum states real numbers suffice. Additionally, we derive lower bounds on the coherence of PRSs and PRUs, ruling out the existence of sparse PRUs and PRSs. We also show that the notions of PRS, PRUs and pseudorandom scramblers (PRSSs) are distinct in terms of resource requirements. We introduce the concept of pseudoresources, where states which contain a low amount of a given resource masquerade as high-resource states. We define pseudocoherence, pseudopurity and pseudoimaginarity, and identify three distinct types of pseudoresources in terms of their masquerading capabilities. Our work also establishes rigorous bounds on the efficiency of property testing, demonstrating the exponential complexity in distinguishing real quantum states from imaginary ones, in contrast to the efficient measurability of unitary imaginarity. Further, we show an exponential advantage in imaginarity testing when having access to the complex conjugate of the state. Lastly, we show that the transformation from a complex to a real model of quantum computation is inefficient, in contrast to the reverse process, which is efficient. Our results establish fundamental limits on property testing and provide valuable insights into quantum pseudorandomness.