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:
 10273623
 Journal Name:
 Proceedings of the National Academy of Sciences
 Volume:
 117
 Issue:
 41
 Page Range or eLocationID:
 25402 to 25406
 ISSN:
 00278424
 Sponsoring Org:
 National Science Foundation
More Like this

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

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. 
A bstract We investigate two sparse SachdevYeKitaev (SYK) systems coupled by a bilinear term as a holographic quantum mechanical description of an eternal traversable wormhole in the low temperature limit. Each SYK system consists of N Majorana fermions coupled by random q body interactions. The degree of sparseness is captured by a regular hypergraph in such a way that the Hamiltonian contains exactly k N independent terms. We improve on the theoretical understanding of the sparseness property by using known measures of hypergraph expansion. We show that the sparse version of the two coupled SYK model is gapped with a ground state close to a thermofield double state. Using Krylov subspace and parallelization techniques, we simulate the system for q = 4 and q = 8. The sparsity of the model allows us to explore larger values of N than the ones existing in the literature for the alltoall SYK. We analyze in detail the twopoint functions and the transmission amplitude of signals between the two systems. We identify a range of parameters where revivals obey the scaling predicted by holography and signals can be interpreted as traversing the wormhole.