 Award ID(s):
 1818914
 Publication Date:
 NSFPAR ID:
 10273618
 Journal Name:
 Proceedings of the National Academy of Sciences
 Volume:
 117
 Issue:
 41
 Page Range or eLocationID:
 25396 to 25401
 ISSN:
 00278424
 Sponsoring Org:
 National Science Foundation
More Like this

Quantum computational supremacy arguments, which describe a way for a quantum computer to perform a task that cannot also be done by a classical computer, typically require some sort of computational assumption related to the limitations of classical computation. One common assumption is that the polynomial hierarchy ( P H ) does not collapse, a stronger version of the statement that P ≠ N P , which leads to the conclusion that any classical simulation of certain families of quantum circuits requires time scaling worse than any polynomial in the size of the circuits. However, the asymptotic nature of this conclusion prevents us from calculating exactly how many qubits these quantum circuits must have for their classical simulation to be intractable on modern classical supercomputers. We refine these quantum computational supremacy arguments and perform such a calculation by imposing finegrained versions of the noncollapse conjecture. Our first two conjectures poly3NSETH( a ) and perintNSETH( b ) take specific classical counting problems related to the number of zeros of a degree3 polynomial in n variables over F 2 or the permanent of an n × n integervalued matrix, and assert that any nondeterministic algorithm that solves them requires 2 c nmore »

Abstract In the nearterm, hybrid quantumclassical algorithms hold great potential for outperforming classical approaches. Understanding how these two computing paradigms work in tandem is critical for identifying areas where such hybrid algorithms could provide a quantum advantage. In this work, we study a QAOAbased quantum optimization approach by implementing the Variational Quantum Factoring (VQF) algorithm. We execute experimental demonstrations using a superconducting quantum processor, and investigate the trade off between quantum resources (number of qubits and circuit depth) and the probability that a given biprime is successfully factored. In our experiments, the integers 1099551473989, 3127, and 6557 are factored with 3, 4, and 5 qubits, respectively, using a QAOA ansatz with up to 8 layers and we are able to identify the optimal number of circuit layers for a given instance to maximize success probability. Furthermore, we demonstrate the impact of different noise sources on the performance of QAOA, and reveal the coherent error caused by the residual
Z Z coupling between qubits as a dominant source of error in a nearterm superconducting quantum processor. 
Variational Quantum Algorithms (VQAs) rely upon the iterative optimization of a parameterized unitary circuit with respect to an objective function. Since quantum machines are noisy and expensive resources, it is imperative to choose a VQA's ansatz appropriately and its initial parameters to be close to optimal. This work tackles the problem of finding initial ansatz parameters by proposing CAFQA, a Clifford ansatz for quantum accuracy. The CAFQA ansatz is a hardwareefficient circuit built with only Clifford gates. In this ansatz, the initial parameters for the tunable gates are chosen by searching efficiently through the Clifford parameter space via classical simulation, thereby producing a suitable stabilizer state. The stabilizer states produced are shown to always equal or outperform traditional classical initialization (e.g., HartreeFock), and often produce high accuracy estimations prior to quantum exploration. Furthermore, the technique is classically suited since a) Clifford circuits can be exactly simulated classically in polynomial time and b) the discrete Clifford space, while scaling exponentially in the number of qubits, is searched efficiently via Bayesian Optimization. For the Variational Quantum Eigensolver (VQE) task of molecular ground state energy estimation up to 20 qubits, CAFQA's Clifford Ansatz achieves a mean accuracy of near 99%, recovering as muchmore »

Abstract Realizing the potential of nearterm quantum computers to solve industryrelevant constrainedoptimization problems is a promising path to quantum advantage. In this work, we consider the extractive summarization constrainedoptimization problem and demonstrate the largesttodate execution of a quantum optimization algorithm that natively preserves constraints on quantum hardware. We report results with the Quantum Alternating Operator Ansatz algorithm with a Hammingweightpreserving XY mixer (XYQAOA) on trappedion quantum computer. We successfully execute XYQAOA circuits that restrict the quantum evolution to the inconstraint subspace, using up to 20 qubits and a twoqubit gate depth of up to 159. We demonstrate the necessity of directly encoding the constraints into the quantum circuit by showing the tradeoff between the inconstraint probability and the quality of the solution that is implicit if unconstrained quantum optimization methods are used. We show that this tradeoff makes choosing good parameters difficult in general. We compare XYQAOA to the Layer Variational Quantum Eigensolver algorithm, which has a highly expressive constantdepth circuit, and the Quantum Approximate Optimization Algorithm. We discuss the respective tradeoffs of the algorithms and implications for their execution on nearterm quantum hardware.

Abstract Quantum Approximate Optimization algorithm (QAOA) aims to search for approximate solutions to discrete optimization problems with nearterm quantum computers. As there are no algorithmic guarantee possible for QAOA to outperform classical computers, without a proof that boundederror quantum polynomial time (BQP) ≠ nondeterministic polynomial time (NP), it is necessary to investigate the empirical advantages of QAOA. We identify a computational phase transition of QAOA when solving hard problems such as SAT—random instances are most difficult to train at a critical problem density. We connect the transition to the controllability and the complexity of QAOA circuits. Moreover, we find that the critical problem density in general deviates from the SATUNSAT phase transition, where the hardest instances for classical algorithms lies. Then, we show that the high problem density region, which limits QAOA’s performance in hard optimization problems (reachability deficits), is actually a good place to utilize QAOA: its approximation ratio has a much slower decay with the problem density, compared to classical approximate algorithms. Indeed, it is exactly in this region that quantum advantages of QAOA over classical approximate algorithms can be identified.