Quantum Approximate Optimization with a Trapped-Ion Quantum Simulator
Guido Pagano, Aniruddha Bapat, Patrick Becker, K. S. Collins, Arinjoy De, Paul Hess, Harvey Kaplan, A. Kyprianidis, Wen Lin Tan, Charles H. Baldwin, Lucas T. Brady, Abhinav Deshpande, F. Liu, Stephen P. Jordan, Alexey Vyacheslavovich Gorshkov, Christopher R. Monroe
Quantum computers and simulators may offer significant advantages over their
classical counterparts, providing insights into quantum many-body systems and
possibly solving exponentially hard problems, such as optimization and
satisfiability. Here we report the first implementation of a shallow-depth
Quantum Approximate Optimization Algorithm (QAOA) using an analog quantum
simulator to estimate the ground state energy of the transverse field Ising
model with tunable long-range interactions. First, we exhaustively search the
variational control parameters to approximate the ground state energy with up
to 40 trapped-ion qubits. We then interface the quantum simulator with a
classical algorithm to more efficiently find the optimal set of parameters that
minimizes the resulting energy of the system. We finally sample from the full
probability distribution of the QAOA output with single-shot and efficient
measurements of every qubit.
Quantum computers and simulators may offer significant advantages over their
classical counterparts, providing insights into quantum many-body systems and
possibly solving exponentially hard problems, such as optimization and
satisfiability. Here we report the first implementation of a shallow-depth
Quantum Approximate Optimization Algorithm (QAOA) using an analog quantum
simulator to estimate the ground state energy of the transverse field Ising
model with tunable long-range interactions. First, we exhaustively search the
variational control parameters to approximate the ground state energy with up
to 40 trapped-ion qubits. We then interface the quantum simulator with a
classical algorithm to more efficiently find the optimal set of parameters that
minimizes the resulting energy of the system. We finally sample from the full
probability distribution of the QAOA output with single-shot and efficient
measurements of every qubit.
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.
Abstract We present Snapshot-QAOA, a variation of the Quantum Approximate Optimization Algorithm (QAOA) that finds approximate minimum energy eigenstates of a large set of quantum Hamiltonians. Traditionally, QAOA targets the task of approximately solving combinatorial optimization problems. Snapshot-QAOA enables a significant expansion of the use case space for QAOA to more general quantum Hamiltonians, where the goal is to approximate the ground-state. Snapshot-QAOA retains the desirable variational-algorithm qualities of QAOA such as a small parameter count and relatively shallow circuit depth. Snapshot-QAOA is thus a better trainable alternative to the (Near Intermediate-Scale Quantum) NISQ-era Variational Quantum Eigensolver (VQE) algorithm, while retaining a significant circuit-depth advantage over the (Quantum Error Corrected) QEC-era Quantum Phase Estimation (QPE) algorithm. Our fundamental approach is inspired by the idea of Trotterization of a continuous-time linear adiabatic anneal schedule. Snapshot-QAOA restricts the QAOA evolution to not phasing out the mixing Hamiltonian completely at the end of the evolution, instead evolving only a partial typical linear QAOA schedule, thus creating a type of snapshot of the typical QAOA evolution. In this way, the cost of the quantum Hamiltonian is encoded by the phase separator to address the diagonal terms in the problem Hamiltonian and by the mixer to address the non-diagonal terms in the problem Hamiltonian. We focus on QAOA with the transverse field mixer, and thus simulations of quantum Hamiltonians that contain single-site Pauli-X terms. By measuring the expectation value of the system in both X and Z-basis, we can estimate the ground-state energy of transverse field quantum Hamiltonians. The accuracy of ground-state energy finding with snapshot-QAOA is evaluated using extensive numerical simulations on a 16 qubit J1-J2 frustrated transverse field Ising model.
Abstract We present Snapshot-QAOA, a variation of the Quantum Approximate Optimization Algorithm (QAOA) that finds approximate minimum energy eigenstates of a large set of quantum Hamiltonians (i.e. Hamiltonians with non-diagonal terms). Traditionally, QAOA targets the task of approximately solving combinatorial optimization problems --- Snapshot-QAOA enables a significant expansion of the use case space for QAOA to more general quantum Hamiltonians, where the goal is to approximate the ground-state. Such ground-state finding is a common challenge in quantum chemistry and material science applications. Snapshot-QAOA retains desirable variational-algorithm qualities of QAOA, in particular small parameter count and relatively shallow circuit depth. Snapshot-QAOA is thus a better trainable alternative to the (Near Intermediate-Scale Quantum) NISQ-era Variational Quantum Eigensolver (VQE) algorithm, while retaining a significant circuit-depth advantage over the (Quantum Error Corrected) QEC-era Quantum Phase Estimation (QPE) algorithm. Our fundamental approach is inspired by the idea of Trotterization of a continuous-time linear adiabatic anneal schedule, which for sufficiently large QAOA depth gives very good performance. Snapshot-QAOA restricts the QAOA evolution to not phasing out the mixing Hamiltonian completely at the end of the evolution, instead evolving only a partial typical linear QAOA schedule, thus creating a type of snapshot of the typical QAOA evolution. As a test case, we simulate Snapshot-QAOA on a particular 16 qubit 2D J1-J2 frustrated square transverse field Ising model with periodic boundary conditions.
We present Snapshot-QAOA, a variation of the Quantum Approximate Optimization Algorithm (QAOA) that finds approximate minimum energy eigenstates of a large set of quantum Hamiltonians (i.e. Hamiltonians with non-diagonal terms). Traditionally, QAOA targets the task of approximately solving combinatorial optimization problems; Snapshot-QAOA enables a significant expansion of the use case space for QAOA to more general quantum Hamiltonians, where the goal is to approximate the ground-state. Such ground-state finding is a common challenge in quantum chemistry and material science applications. Snapshot-QAOA retains desirable variational-algorithm qualities of QAOA, in particular small parameter count and relatively shallow circuit depth. Snapshot-QAOA is thus a better trainable alternative to the NISQ-era Variational Quantum Eigensolver (VQE) algorithm, while retaining a significant circuit-depth advantage over the QEC-era Quantum Phase Estimation (QPE) algorithm. Our fundamental approach is inspired by the idea of Trotterization of a continuous-time linear adiabatic anneal schedule, which for sufficiently large QAOA depth gives very good performance. Snapshot-QAOA restricts the QAOA evolution to not phasing out the mixing Hamiltonian completely at the end of the evolution, instead evolving only a partial typical linear QAOA schedule, thus creating a type of snapshot of the typical QAOA evolution. As a test case, we simulate Snapshot-QAOA on a 16 qubit J1-J2 frustrated square transverse field Ising model with periodic boundary conditions.
State preparation protocols ideally require as minimal operations as possible, in order to be implemented in near-term, potentially noisy quantum devices. Motivated by long range interactions (LRIs) intrinsic to many present-day experimental platforms (trapped ions, Rydberg atom arrays, etc.), we investigate the efficacy of variationally simulating non-trivial quantum states using the Variational Quantum-Classical Simulation (VQCS) protocol explored recently in [SciPost Phys. 6, 029 (2019)], in the presence of LRIs. We show that this approach leads to extremely efficient state preparation: for example, Greene-Horne-Zeilinger (GHZ) states can be prepared with O(1) iterations of the protocol, and a quantum critical point of the long range transverse field Ising model (TFIM) can be prepared with > 99% fidelity on a 100 qubit system with only one iteration. Furthermore, we show that VQCS with LRIs is a promising route for exploring generic points in the phase diagram of the long-range TFIM. Our approach thus provides concrete, ultrafast protocols for quantum simulators equipped with long range interactions.
The quantum approximate optimization algorithm (QAOA) is a quantum heuristic for combinatorial optimization that has been demonstrated to scale better than state-of-the-art classical solvers for some problems. For a given problem instance, QAOA performance depends crucially on the choice of the parameters. While average-case optimal parameters are available in many cases, meaningful performance gains can be obtained by fine-tuning these parameters for a given instance. This task is especially challenging, however, when the number of circuit executions (shots) is limited. In this work, we develop an end-to-end protocol that combines multiple parameter settings and fine-tuning techniques. We use large-scale numerical experiments to optimize the protocol for the shot-limited setting and observe that optimizers with the simplest internal model (linear) perform best. We implement the optimized pipeline on a trapped-ion processor using up to 32 qubits and 5 QAOA layers, and we demonstrate that the pipeline is robust to small amounts of hardware noise. To the best of our knowledge, these are the largest demonstrations of QAOA parameter fine-tuning on a trapped-ion processor in terms of two-qubit gate count.