We show how a digitized version of Quantum Annealing can be made optimal, realizing the best possible solution allowed by quantum mechanics in the shortest time, without any prior knowledge on the location and properties of the spectral gap. Our findings elucidate the intimate relation between digitized-QA, optimal Quantum Control, and recently proposed hybrid quantum-classical variational algorithms for quantum-state preparation and optimization. We illustrate this on the simple benchmark problem of an unfrustrated antiferromagnetic Ising chain in a transverse field.
We show how a digitized version of Quantum Annealing can be made optimal, realizing the best possible solution allowed by quantum mechanics in the shortest time, without any prior knowledge on the location and properties of the spectral gap. Our findings elucidate the intimate relation between digitized-QA, optimal Quantum Control, and recently proposed hybrid quantum-classical variational algorithms for quantum-state preparation and optimization. We illustrate this on the simple benchmark problem of an unfrustrated antiferromagnetic Ising chain in a transverse field.
We establish and discuss a number of connections between a digitized version of Quantum Annealing (QA) with the Quantum Approximate Optimization Algorithm (QAOA) introduced by Farhi et al. (arXiv:1411.4028) as an alternative hybrid quantum-classical variational scheme for quantum-state preparation and optimization. We introduce a technique that allows to prove, for instance, a rigorous bound concerning the performance of QAOA for MaxCut on a 2-regular graph, equivalent to an unfrustrated antiferromagnetic Ising chain. The bound shows that the optimal variational error of a depth-P quantum circuit has to satisfy εPres≥(2P+2)−1. In a separate work (Mbeng et al., arXiv:1911.12259) we have explicitly shown, exploiting a Jordan-Wigner transformation, that among the 2P degenerate variational minima which can be found for this problem, all strictly satisfying the equality εPres=(2P+2)−1, one can construct a special {\em regular} optimal solution, which is computationally optimal and does not require any prior knowledge about the spectral gap. We explicitly demonstrate here that such a schedule is adiabatic, in a digitized sense, and can therefore be interpreted as an optimized digitized-QA protocol. We also discuss and compare our bound on the residual energy to well-known results on the Kibble-Zurek mechanism behind a continuous-time QA. These findings help elucidating the intimate relation between digitized-QA, QAOA, and optimal Quantum Control.
The recent advances in the world of quantum technologies have prompted the development of various quantum-based algorithms, some of which are suitable to run on available quantum devices. Two leading candidates in this area are Quantum Annealing (QA) and hybrid quantum-classical variational algorithms, such as the Quantum Approximate Optimization Algorithm (QAOA). In the first part of the Thesis, we re-examine the issue of whether Simulated Quantum Annealing (SQA) with Path Integral Monte Carlo has anything to do with the coherent QA Schrödinger dynamics. We do that by studying the random quantum Ising Chain in a transverse field. In the second part of the Thesis we address the issue of schedule optimization in both {em digitized}-QA and QAOA. Traditional schedule optimization in QA requires spectral information on the problem (e.g., location of the minimum gaps), which is in most cases inaccessible. On the other hand, in QAOA, the issue of schedule optimization --- alias, the optimization of the variational parameters --- is often an expensive task that constitutes a bottleneck for the algorithm. We show that, by combining the framework of QAOA and digitized-QA, optimal digitized-QA protocols can be constructed efficiently. When using this approach, the computational cost of schedule optimization is also significantly reduced, leading to a computational advantage both over a linear-schedule QA, and over an unstructured QAOA search. While studying these issues, we also developed rigorous variational bounds that provide insight on the best possible performance that one can hope to obtain from a digital QAOA circuit.
Recent advances in quantum technologies have intensified the search for algo rithms that can use quantum resources effectively. Quantum annealing and hybrid quantum–classical variational algorithms are two prominent approaches in this set ting. Conventional quantum annealing follows a prescribed Hamiltonian interpo lation and may therefore be limited by small spectral gaps along that path. This Thesis investigates how algorithmic performance changes when three elements are varied: the annealing schedule (Chapter 2), the independent parameters of a digi tized evolution (Chapter 3), and the encoding of the problem (Chapter 4). For weighted MaxCut instances with anomalously small annealing gaps, opti mized smooth schedules outperform linear digitized annealing at equal circuit depth. Rather than restoring adiabaticity or enlarging the gap, the dynamics deliberately leaves the instantaneous ground state and later returns the population to the target state. Smoothness allows these digital solutions to retain their quality as continuous time controls and when transferred between related instances. The schedule restriction is then removed for a frustrated Ising ring whose anneal ing gap closes exponentially with system size. Optimizing all circuit angles inde pendently yields numerically exact ground-state preparation at the critical depth Pcr 1 =(N2−1)/4. This quadratic threshold is explained by the dimension and sym metries of the reachable free-fermion manifold, demonstrating that controllability, rather than the gap of a particular interpolation, determines the required number of digital controls. Finally, the same ring family is reformulated through the parity mapping. For the original frustrated ring, Parity-QAOA reaches the exact ground state using only single-qubit rotations, without applying the constraint unitary. The number of layers equals the number of distinct coupling values and does not grow with system size. To clarify the role of constraints, an equal-magnitude signed ring is also studied, for which the constraint unitary is essential for preparing the target ground state. Together, these results identify the shape, controllability, and encoding of a quan tum protocol as resources for overcoming limitations imposed by more restricted routes to ground-state preparation.
Abstract Quantum Annealing (QA) relies on mixing two Hamiltonian terms, a simple driver and a complex problem Hamiltonian, in a linear combination. The time-dependent schedule for this mixing is often taken to be linear in time: improving on this linear choice is known to be essential and has proven to be difficult. Here, we present different techniques for improving on the linear-schedule QA along two directions, conceptually distinct but leading to similar outcomes: 1) the first approach consists of constructing a Trotter-digitized QA (dQA) with schedules parameterized in terms of Fourier modes or Chebyshev polynomials, inspired by the Chopped Random Basis algorithm for optimal control in continuous time; 2) the second approach is technically a Quantum Approximate Optimization Algorithm (QAOA), whose solutions are found iteratively using linear interpolation or expansion in Fourier modes. Both approaches emphasize finding smooth optimal schedule parameters, ultimately leading to hybrid quantum–classical variational algorithms of the alternating Hamiltonian Ansatz type. We apply these techniques to MaxCut problems on weighted 3-regular graphs with N = 14 sites, focusing on hard instances that exhibit a small spectral gap, for which a standard linear-schedule QA performs poorly. We characterize the physics behind the optimal protocols for both the dQA and QAOA approaches, discovering shortcuts to adiabaticity -like dynamics. Furthermore, we study the transferability of such smooth solutions among hard instances of MaxCut at different circuit depths. Finally, we show that the smoothness pattern of these protocols obtained in a digital setting enables us to adapt them to continuous-time evolution, contrarily to generic non-smooth solutions. This procedure results in an optimized QA schedule that is implementable on analog devices.
Abstract Exponentially small spectral gaps are known to be the crucial bottleneck for traditional Quantum Annealing (QA) based on interpolating between two Hamiltonians, a simple driving term and the complex problem to be solved, with a linear schedule in time. One of the simplest models exhibiting exponentially small spectral gaps is a ferromagnetic Ising ring with a single antiferromagnetic bond introducing frustration. Previous studies of this model have explored continuous-time diabatic QA, where optimized non-adiabatic annealing schedules provided good solutions, avoiding exponentially large annealing times. In our work, we move to a digital framework of Variational Quantum Algorithms, and present two main results: (1) we show that the model is digitally controllable with a scaling of resources that grows quadratically with the system size, achieving the exact solution using the Quantum Approximate Optimization Algorithm; (2) We combine a technique of quantum control—the Chopped RAndom Basis method—and digitized quantum annealing to construct smooth digital schedules yielding optimal solutions with very high accuracy.
We present a study of the digitized quantum annealing protocol proposed by R. Barends et al. [Nature (London) 534, 222 (2016)]. Our analysis, performed on the benchmark case of a transverse Ising chain problem, shows that the algorithm has a well-defined optimal working point for the annealing time ${\ensuremath{\tau}}_{\mathrm{P}}^{\mathrm{opt}}$, scaling as ${\ensuremath{\tau}}_{\mathrm{P}}^{\mathrm{opt}}\ensuremath{\sim}\mathrm{P}$, where P is the number of digital Trotter steps, beyond which the residual energy error shoots up toward the value characteristic of the maximally disordered state. We present an analytical analysis for the translationally invariant transverse Ising chain case, but our numerical evidence suggests that this scenario is more general, surviving, for instance, the presence of disorder.