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.
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.
Continuous-time Quantum Annealing (QA) is a strategy for preparing the ground state of nontrivial many-body systems. In its standard form, the dynamics is generated by a time-dependent interpolation between a simple driving Hamiltonian and the target problem Hamiltonian, usually implemented through a linear schedule. This approach faces the crucial bottleneck of small spectral gaps, which may require exponentially long annealing times to ensure adiabaticity. Here, we show how to implement quantum control over the annealing schedule in a frustrated Ising ring, one of the simplest models exhibiting an exponentially small bottleneck gap. By optimizing smooth continuous-time annealing schedules with a dressed-CRAB approach, and using a digitized representation of the dynamics to efficiently evaluate gradients, we construct protocols that strongly outperform standard fixed schedules. The optimized dynamics bypasses the bottleneck through a strongly nonadiabatic mechanism, leading to efficient ground-state preparation despite the exponentially small minimum gap. In particular, the annealing time required to reach a fixed residual-energy threshold is found to grow linearly with system size rather than exponentially. We further examine a lowest-order variational counter-diabatic correction and find that, once schedule optimization is allowed, it does not lead to any improvement.
We investigate the role of local counter-diabatic (CD) terms in enhancing the performance of discrete-time digital protocols for a frustrated Ising ring, a system with an exponentially small spectral gap that acts as a bottleneck for conventional quantum annealing. The techniques investigated range from a digitised version of a fixed-schedule protocol, including lowest-order analytical CD terms, all the way to a full-fledged Quantum Approximate Optimisation Algorithm (QAOA), including variational CD terms (DC-QAOA). By analyzing the resulting residual energy, we show that DC-QAOA combined with Chopped RAndom Basis (CRAB) quantum control techniques for optimizing the circuit parameters, can outperform all the other strategies. By monitoring the ground-state population during the dynamics we learn that DC-QAOA finds effective shortcuts towards the target state through intermediate excited states, a process that is unexpectedly enhanced by the inclusion of local CD unitaries. Our results highlight the importance of flexible variational control of CD dynamics and demonstrate that digital optimization can explore operator dynamics that remain inaccessible to standard analytical CD constructions.
Abstract Quantum annealing (QA) is a continuous-time heuristic quantum algorithm for solving or approximately solving classical optimization problems. The algorithm uses a schedule to interpolate between a driver Hamiltonian with an easy-to-prepare ground state and a problem Hamiltonian whose ground state encodes solutions to an optimization problem. The standard implementation relies on the evolution being adiabatic: keeping the system in the instantaneous ground state with high probability and requiring a time scale inversely related to the minimum energy gap between the instantaneous ground and excited states. However, adiabatic evolution can lead to evolution times that scale exponentially with the system size, even for computationally simple problems. Here, we study whether non-adiabatic evolutions with optimized annealing schedules can bypass this exponential slowdown for one such class of problems called the frustrated ring model. For sufficiently optimized annealing schedules and system sizes of up to 39 qubits, we provide numerical evidence that we can avoid the exponential slowdown. Our work highlights the potential of highly-controllable QA to circumvent bottlenecks associated with the standard implementation of QA.
The frustrated Ising ring is one of the simplest models exhibiting exponential closing spectral gaps, making it a paradigmatic and challenging benchmark for quantum annealing (QA). Ground-state preparation for this model has therefore been studied extensively in both continuous-time QA and digitized protocols such as the Quantum Approximate Optimization Algorithm (QAOA). Here, we use the frustrated Ising ring to investigate how the parity mapping affects the performance of both QA and QAOA. For QA, finite-size calculations show that the parity mapping increases the minimum spectral gap under the energy normalization used in this work, thereby enabling faster continuous-time ground state preparation protocols. An ideal implementation of Parity-QA, with a single global constraint, shows no evidence of exponential gap closing over the accessible system sizes, whereas a hardware-motivated decomposition into local constraints restores the exponential decrease, albeit with a smaller fitted exponent than conventional QA. For the digitized protocol, we find that the number of Parity-QAOA layers required to prepare the exact ground state remains constant over the simulated sizes, improving upon the quadratic scaling required by conventional QAOA. To investigate the role of constraints in Parity-QAOA, we further consider a modified Ising ring instance in which the constraint term is essential for preparing the target ground state. We then compare the corresponding resource requirements with those of conventional QAOA.
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.
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.