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.
 Award ID(s):
 1818914
 Publication Date:
 NSFPAR ID:
 10339341
 Journal Name:
 Quantum
 Volume:
 6
 Page Range or eLocationID:
 635
 ISSN:
 2521327X
 Sponsoring Org:
 National Science Foundation
More Like this

Abstract 
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.

We demonstrate that with an optimally tuned scheduling function, adiabatic quantum computing (AQC) can readily solve a quantum linear system problem (QLSP) with O (κ poly(log (κ ε))) runtime, where κ is the condition number, and ε is the target accuracy. This is near optimal with respect to both κ and ε, and is achieved without relying on complicated amplitude amplification procedures that are difficult to implement. Our method is applicable to general nonHermitian matrices, and the cost as well as the number of qubits can be reduced when restricted to Hermitian matrices, and further to Hermitian positive definite matrices. The success of the timeoptimal AQC implies that the quantum approximate optimization algorithm (QAOA) with an optimal control protocol can also achieve the same complexity in terms of the runtime. Numerical results indicate that QAOA can yield the lowest runtime compared to the timeoptimal AQC, vanilla AQC, and the recently proposed randomization method.

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 Quantum annealing is a powerful alternative model of quantum computing, which can succeed in the presence of environmental noise even without error correction. However, despite great effort, no conclusive demonstration of a quantum speedup (relative to state of the art classical algorithms) has been shown for these systems, and rigorous theoretical proofs of a quantum advantage (such as the adiabatic formulation of Grover’s search problem) generally rely on exponential precision in at least some aspects of the system, an unphysical resource guaranteed to be scrambled by experimental uncertainties and random noise. In this work, we propose a new variant of quantum annealing, called RFQA, which can maintain a scalable quantum speedup in the face of noise and modest control precision. Specifically, we consider a modification of flux qubitbased quantum annealing which includes lowfrequency oscillations in the directions of the transverse field terms as the system evolves. We show that this method produces a quantum speedup for finding ground states in the Grover problem and quantum random energy model, and thus should be widely applicable to other hard optimization problems which can be formulated as quantum spin glasses. Further, we explore three realistic noise channels and show that the speedupmore »