Quantum annealing (QA) and the quantum approximate optimization algorithm (QAOA) are two special cases of the following control problem: apply a combination of two Hamiltonians to minimize the energy of a quantum state. Which is more effective has remained unclear. Here we analytically apply the framework of optimal control theory to show that generically, given a fixed amount of time, the optimal procedure has the pulsed (or {\textquotedblleft}bang-bang{\textquotedblright}) structure of QAOA at the beginning and end but can have a smooth annealing structure in between. This is in contrast to previous works which have suggested that bang-bang (i.e., QAOA) protocols are ideal. To support this theoretical work, we carry out simulations of various transverse field Ising models, demonstrating that bang-anneal-bang protocols are more common. The general features identified here provide guideposts for the nascent experimental implementations of quantum optimization algorithms.

}, issn = {0031-9007}, doi = {10.1103/PhysRevLett.126.070505}, author = {Brady, Lucas T. and Baldwin, Christopher L. and Bapat, Aniruddha and Kharkov, Yaroslav and Gorshkov, Alexey V} } @article { WOS:000691579200002, title = {Quantum routing with fast reversals}, journal = {Quantum}, volume = {5}, year = {2021}, month = {AUG 31}, publisher = {VEREIN FORDERUNG OPEN ACCESS PUBLIZIERENS QUANTENWISSENSCHAF}, type = {Article}, abstract = {We present methods for implementing arbitrary permutations of qubits under interaction constraints. Our protocols make use of previous methods for rapidly reversing the order of qubits along a path. Given nearest-neighbor interactions on a path of length n, we show that there exists a constant epsilon approximate to 0.034 such that the quantum routing time is at most (1 - epsilon)n, whereas any SWAP-based protocol needs at least time n - 1. This represents the first known quantum advantage over SWAP-based routing methods and also gives improved quantum routing times for realistic architectures such as grids. Furthermore, we show that our algorithm approaches a quantum routing time of 2n/3 in expectation for uniformly random permutations, whereas SWAP-based protocols require time n asymptotically. Additionally, we consider sparse permutations that route k <= n qubits and give algorithms with quantum routing time at most n/3 + O(k(2)) on paths and at most 2r/3 + O(k(2)) on general graphs with radius r.}, issn = {2521-327X}, author = {Bapat, Aniruddha and Childs, Andrew M. and V. Gorshkov, Alexey and King, Samuel and Schoute, Eddie and Shastri, Hrishee} } @article {eldredge_entanglement_2020, title = {Entanglement bounds on the performance of quantum computing architectures}, journal = {Phys. Rev. Res.}, volume = {2}, number = {3}, year = {2020}, note = {Place: ONE PHYSICS ELLIPSE, COLLEGE PK, MD 20740-3844 USA Publisher: AMER PHYSICAL SOC Type: Article}, month = {aug}, abstract = {There are many possible architectures of qubit connectivity that designers of future quantum computers will need to choose between. However, the process of evaluating a particular connectivity graph{\textquoteright}s performance as a quantum architecture can be difficult. In this paper, we show that a quantity known as the isoperimetric number establishes a lower bound on the time required to create highly entangled states. This metric we propose counts resources based on the use of two-qubit unitary operations, while allowing for arbitrarily fast measurements and classical feedback. We use this metric to evaluate the hierarchical architecture proposed by A. Bapat et al. [Phys. Rev. A 98, 062328 (2018)] and find it to be a promising alternative to the conventional grid architecture. We also show that the lower bound that this metric places on the creation time of highly entangled states can be saturated with a constructive protocol, up to a factor logarithmic in the number of qubits.}, doi = {10.1103/PhysRevResearch.2.033316}, author = {Eldredge, Zachary and Zhou, Leo and Bapat, Aniruddha and Garrison, James R. and Deshpande, Abhinav and Chong, Frederic T. and Gorshkov, V, Alexey} } @article {pagano_quantum_2020, title = {Quantum approximate optimization of the long-range {Ising} model with a trapped-ion quantum simulator}, journal = {Proc. Natl. Acad. Sci. U. S. A.}, volume = {117}, number = {41}, year = {2020}, note = {Place: 2101 CONSTITUTION AVE NW, WASHINGTON, DC 20418 USA Publisher: NATL ACAD SCIENCES Type: Article}, month = {oct}, pages = {25396{\textendash}25401}, abstract = {Quantum computers and simulators may offer significant advantages over their classical counterparts, providing insights into quantum many-body systems and possibly improving performance for solving exponentially hard problems, such as optimization and satisfiability. Here, we report the implementation of a low-depth Quantum Approximate Optimization Algorithm (QAOA) using an analog quantum simulator. We estimate the ground-state energy of the Transverse Field Ising Model with long-range interactions with tunable range, and we optimize the corresponding combinatorial classical problem by sampling the QAOA output with high-fidelity, single-shot, individual qubit measurements. We execute the algorithm with both an exhaustive search and closed-loop optimization of the variational parameters, approximating the ground-state energy with up to 40 trapped-ion qubits. We benchmark the experiment with bootstrapping heuristic methods scaling polynomially with the system size. We observe, in agreement with numerics, that the QAOA performance does not degrade significantly as we scale up the system size and that the runtime is approximately independent from the number of qubits. We finally give a comprehensive analysis of the errors occurring in our system, a crucial step in the path forward toward the application of the QAOA to more general problem instances.}, keywords = {computing, quantum, quantum algorithms, quantum information science, quantum simulation, trapped ions}, issn = {0027-8424}, doi = {10.1073/pnas.2006373117}, author = {Pagano, Guido and Bapat, Aniruddha and Becker, Patrick and Collins, Katherine S. and De, Arinjoy and Hess, Paul W. and Kaplan, Harvey B. and Kyprianidis, Antonis and Tan, Wen Lin and Baldwin, Christopher and Brady, Lucas T. and Deshpande, Abhinav and Liu, Fangli and Jordan, Stephen and Gorshkov, V, Alexey and Monroe, Christopher} } @article { ISI:000454419500004, title = {Unitary entanglement construction in hierarchical networks}, journal = {PHYSICAL REVIEW A}, volume = {98}, number = {6}, year = {2018}, month = {DEC 26}, pages = {062328}, abstract = {The construction of large-scale quantum computers will require modular architectures that allow physical resources to be localized in easy-to-manage packages. In this work we examine the impact of different graph structures on the preparation of entangled states. We begin by explaining a formal framework, the hierarchical product, in which modular graphs can be easily constructed. This framework naturally leads us to suggest a class of graphs, which we dub hierarchies. We argue that such graphs have favorable properties for quantum information processing, such as a small diameter and small total edge weight, and use the concept of Pareto efficiency to identify promising quantum graph architectures. We present numerical and analytical results on the speed at which large entangled states can be created on nearest-neighbor grids and hierarchy graphs. We also present a scheme for performing circuit placement-the translation from circuit diagrams to machine qubits-on quantum systems whose connectivity is described by hierarchies.}, issn = {2469-9926}, doi = {10.1103/PhysRevA.98.062328}, author = {Bapat, Aniruddha and Eldredge, Zachary and Garrison, James R. and Deshpande, Abhinav and Chong, Frederic T. and Gorshkov, Alexey V.} }