%0 Journal Article %D 2022 %T Estimating gate complexities for the site-by-site preparation of fermionic vacua %A Troy Sewell %A Aniruddha Bapat %A Stephen Jordan %X

An important aspect of quantum simulation is the preparation of physically interesting states on a quantum computer, and this task can often be costly or challenging to implement. A digital, ``site-by-site'' scheme of state preparation was introduced in arXiv:1911.03505 as a way to prepare the vacuum state of certain fermionic field theory Hamiltonians with a mass gap. More generally, this algorithm may be used to prepare ground states of Hamiltonians by adding one site at a time as long as successive intermediate ground states share a non-zero overlap and the Hamiltonian has a non-vanishing spectral gap at finite lattice size. In this paper, we study the ground state overlap as a function of the number of sites for a range of quadratic fermionic Hamiltonians. Using analytical formulas known for free fermions, we are able to explore the large-N behavior and draw conclusions about the state overlap. For all models studied, we find that the overlap remains large (e.g. >0.1) up to large lattice sizes (N=64,72) except near quantum phase transitions or in the presence of gapless edge modes. For one-dimensional systems, we further find that two N/2-site ground states also share a large overlap with the N-site ground state everywhere except a region near the phase boundary. Based on these numerical results, we additionally propose a recursive alternative to the site-by-site state preparation algorithm.

%8 07/04/2022 %G eng %U https://arxiv.org/abs/2207.01692 %0 Journal Article %D 2021 %T Behavior of Analog Quantum Algorithms %A Lucas T. Brady %A Lucas Kocia %A Przemyslaw Bienias %A Aniruddha Bapat %A Yaroslav Kharkov %A Alexey V. Gorshkov %X

Analog quantum algorithms are formulated in terms of Hamiltonians rather than unitary gates and include quantum adiabatic computing, quantum annealing, and the quantum approximate optimization algorithm (QAOA). These algorithms are promising candidates for near-term quantum applications, but they often require fine tuning via the annealing schedule or variational parameters. In this work, we explore connections between these analog algorithms, as well as limits in which they become approximations of the optimal procedure.Notably, we explore how the optimal procedure approaches a smooth adiabatic procedure but with a superposed oscillatory pattern that can be explained in terms of the interactions between the ground state and first excited state that effect the coherent error cancellation of diabatic transitions. Furthermore, we provide numeric and analytic evidence that QAOA emulates this optimal procedure with the length of each QAOA layer equal to the period of the oscillatory pattern. Additionally, the ratios of the QAOA bangs are determined by the smooth, non-oscillatory part of the optimal procedure. We provide arguments for these phenomena in terms of the product formula expansion of the optimal procedure. With these arguments, we conclude that different analog algorithms can emulate the optimal protocol under different limits and approximations. Finally, we present a new algorithm for better approximating the optimal protocol using the analytic and numeric insights from the rest of the paper. In practice, numerically, we find that this algorithm outperforms standard QAOA and naive quantum annealing procedures. 

%8 7/2/2021 %G eng %U https://arxiv.org/abs/2107.01218 %0 Journal Article %J Quantum %D 2021 %T Quantum routing with fast reversals %A Aniruddha Bapat %A Andrew M. Childs %A Alexey V. Gorshkov %A Samuel King %A Eddie Schoute %A Hrishee Shastri %X

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 ϵ≈0.034 such that the quantum routing time is at most (1−ϵ)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(k2) on paths and at most 2r/3+O(k2) on general graphs with radius r.

%B Quantum %V 5 %8 8/24/2021 %G eng %U https://arxiv.org/abs/2103.03264 %& 533 %R https://doi.org/10.22331/q-2021-08-31-533 %0 Journal Article %D 2020 %T Approximate optimization of MAXCUT with a local spin algorithm %A Aniruddha Bapat %A Stephen P. Jordan %X

Local tensor methods are a class of optimization algorithms that was introduced in [Hastings,arXiv:1905.07047v2][1] as a classical analogue of the quantum approximate optimization algorithm (QAOA). These algorithms treat the cost function as a Hamiltonian on spin degrees of freedom and simulate the relaxation of the system to a low energy configuration using local update rules on the spins. Whereas the emphasis in [1] was on theoretical worst-case analysis, we here investigate performance in practice through benchmarking experiments on instances of the MAXCUT problem.Through heuristic arguments we propose formulas for choosing the hyperparameters of the algorithm which are found to be in good agreement with the optimal choices determined from experiment. We observe that the local tensor method is closely related to gradient descent on a relaxation of maxcut to continuous variables, but consistently outperforms gradient descent in all instances tested. We find time to solution achieved by the local tensor method is highly uncorrelated with that achieved by a widely used commercial optimization package; on some MAXCUT instances the local tensor method beats the commercial solver in time to solution by up to two orders of magnitude and vice-versa. Finally, we argue that the local tensor method closely follows discretized, imaginary-time dynamics of the system under the problem Hamiltonian.

%8 8/13/2020 %G eng %U https://arxiv.org/abs/2008.06054 %0 Journal Article %J Phys. Rev. Research %D 2020 %T Entanglement Bounds on the Performance of Quantum Computing Architectures %A Zachary Eldredge %A Leo Zhou %A Aniruddha Bapat %A James R. Garrison %A Abhinav Deshpande %A Frederic T. Chong %A Alexey V. Gorshkov %X

There are many possible architectures for future quantum computers that designers will need to choose between. However, the process of evaluating a particular connectivity graph's performance as a quantum architecture can be difficult. In this paper, we establish a connection between a quantity known as the isoperimetric number and a lower bound on the time required to create highly entangled states. The metric we propose counts resources based on the use of two-qubit unitary operations, while allowing for arbitrarily fast measurements and classical feedback. We describe how these results can be applied to the evaluation of the hierarchical architecture proposed in Phys. Rev. A 98, 062328 (2018). We also show that the time-complexity bound we place on the creation of highly-entangled states can be saturated up to a multiplicative factor logarithmic in the number of qubits.

%B Phys. Rev. Research %V 2 %8 9/22/2020 %G eng %U https://arxiv.org/abs/1908.04802 %N 033316 %R https://doi.org/10.1103/PhysRevResearch.2.033316 %0 Journal Article %J accepted for publication in Physical Review Research %D 2020 %T Nearly optimal time-independent reversal of a spin chain %A Aniruddha Bapat %A Eddie Schoute %A Alexey V. Gorshkov %A Andrew M. Childs %X

We propose a time-independent Hamiltonian protocol for the reversal of qubit ordering in a chain of N spins. Our protocol has an easily implementable nearest-neighbor, transverse-field Ising model Hamiltonian with time-independent, non-uniform couplings. Under appropriate normalization, we implement this state reversal three times faster than a naive approach using SWAP gates, in time comparable to a protocol of Raussendorf [Phys. Rev. A 72, 052301 (2005)] that requires dynamical control. We also prove lower bounds on state reversal by using results on the entanglement capacity of Hamiltonians and show that we are within a factor 1.502(1+1/N) of the shortest time possible. Our lower bound holds for all nearest-neighbor qubit protocols with arbitrary finite ancilla spaces and local operations and classical communication. Finally, we extend our protocol to an infinite family of nearest-neighbor, time-independent Hamiltonian protocols for state reversal. This includes chains with nearly uniform coupling that may be especially feasible for experimental implementation. 

%B accepted for publication in Physical Review Research %8 3/5/2020 %G eng %U https://arxiv.org/abs/2003.02843 %0 Journal Article %D 2020 %T Optimal Protocols in Quantum Annealing and QAOA Problems %A Lucas T. Brady %A Christopher L. Baldwin %A Aniruddha Bapat %A Yaroslav Kharkov %A Alexey V. Gorshkov %X

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 apply the framework of optimal control theory to show that generically, given a fixed amount of time, the optimal procedure has the pulsed (or "bang-bang") 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. Through simulations of various transverse field Ising models, we demonstrate that bang-anneal-bang protocols are more common. The general features identified here provide guideposts for the nascent experimental implementations of quantum optimization algorithms.

%8 3/19/2020 %G eng %U https://arxiv.org/abs/2003.08952 %0 Journal Article %J Quantum Information & Computation %D 2019 %T Bang-bang control as a design principle for classical and quantum optimization algorithms %A Aniruddha Bapat %A Stephen Jordan %X

Physically motivated classical heuristic optimization algorithms such as simulated annealing (SA) treat the objective function as an energy landscape, and allow walkers to escape local minima. It has been argued that quantum properties such as tunneling may give quantum algorithms advantage in finding ground states of vast, rugged cost landscapes. Indeed, the Quantum Adiabatic Algorithm (QAO) and the recent Quantum Approximate Optimization Algorithm (QAOA) have shown promising results on various problem instances that are considered classically hard. Here, we argue that the type of control strategy used by the optimization algorithm may be crucial to its success. Along with SA, QAO and QAOA, we define a new, bang-bang version of simulated annealing, BBSA, and study the performance of these algorithms on two well-studied problem instances from the literature. Both classically and quantumly, the successful control strategy is found to be bang-bang, exponentially outperforming the quasistatic analogues on the same instances. Lastly, we construct O(1)-depth QAOA protocols for a class of symmetric cost functions, and provide an accompanying physical picture.

%B Quantum Information & Computation %V 19 %P 424-446 %8 8/1/2019 %G eng %U https://arxiv.org/abs/1812.02746 %N 5&6 %0 Journal Article %D 2018 %T Unitary Entanglement Construction in Hierarchical Networks %A Aniruddha Bapat %A Zachary Eldredge %A James R. Garrison %A Abhinav Desphande %A Frederic T. Chong %A Alexey V. Gorshkov %X

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.

%G eng %U https://arxiv.org/abs/1808.07876 %0 Journal Article %J 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014) %D 2014 %T Classical simulation of Yang-Baxter gates %A Gorjan Alagic %A Aniruddha Bapat %A Stephen P. Jordan %X A unitary operator that satisfies the constant Yang-Baxter equation immediately yields a unitary representation of the braid group B n for every $n \ge 2$. If we view such an operator as a quantum-computational gate, then topological braiding corresponds to a quantum circuit. A basic question is when such a representation affords universal quantum computation. In this work, we show how to classically simulate these circuits when the gate in question belongs to certain families of solutions to the Yang-Baxter equation. These include all of the qubit (i.e., $d = 2$) solutions, and some simple families that include solutions for arbitrary $d \ge 2$. Our main tool is a probabilistic classical algorithm for efficient simulation of a more general class of quantum circuits. This algorithm may be of use outside the present setting. %B 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014) %V 27 %P 161-175 %8 2014/07/05 %G eng %U http://arxiv.org/abs/1407.1361v1 %! 9th Conference on the Theory of Quantum Computation %R 10.4230/LIPIcs.TQC.2014.161