Session D51: Hybrid Classical-Quantum Algorithms and Applications

Recent developments in adaptive variational quantum algorithms

The performance of variational quantum algorithms relies on the variational ansatz, which generally needs to be specific to the target problem for easier optimization, and at the same time feasible to be run on noisy quantum processors. To efficiently incorporate the knowledge about the problem into the ansatz, an Adaptive Derivative-Assembled Problem-Tailored (ADAPT) strategy has been developed. It constructs the ansatz iteratively based on the gradient of the objective function, producing compact ansatze and saving resources. In this talk I will briefly review the application of the ADAPT strategy in both variational quantum eigensolver (VQE) and quantum approximation optimization algorithm (QAOA). Then I will discuss some recent developments in terms of operator selection and the impact of the initial state.   

Dramatically reducing the number of measurements in ADAPT-VQE

ADAPT-VQE is a leading variational algorithm that circumvents the choice-of-ansatz conundrum by iteratively growing compact and arbitrarily accurate problem-tailored ansätze. However, the gradient-measurement step of the algorithm requires the estimation of O(N⁸) observables, which hinders the scaling of the algorithm to system sizes of practical interest. In this work we present an efficient strategy for measuring the pool gradients based on a partitioning of the relevant observables into mutually commuting sets. We argue that our approach is robust to shot-noise, and show that measuring the pool gradients is in fact only O(N) times as expensive as a naïve VQE iteration.   

Leveraging Full Data Utilization for Enhanced Performance in Quantum Approximate Optimization Algorithms

The Quantum Approximate Optimization Algorithm (QAOA) is a hybrid classical-quantum approach for addressing complex problems by integrating classical and quantum computing resources. A quantum circuit with classical parameters is executed. Using the most likely measurement output, the parametners are optimized with classical methods. Finally, one iterates until convergence. We address the challenge of flat probability distributions for large system sizes, where choosing the most likely bitstring becomes impractical. Standard QAOA typically discards intermediate values for the cost of each basis state. In contrast, we retain the smallest cost basis state throughout the algorithm's iterations. By focusing on this tailored approach, this adaptation of QAOA consistently delivers improved solutions without incurring additional computational or financial cost. This research demonstrates the algorithm's reliability and reproducibility through the lens of the aircraft loading optimization problem of Airbus's 2020 Quantum Comptuing Challenge executed on Rigetti's Aspen M-3 quantum processor.   

ADAPT-QSCI: Adaptive Construction of Input State for Quantum-Selected Configuration Interaction

We present a quantum-classical hybrid algorithm for calculating the ground state and its energy of the quantum many-body Hamiltonian by proposing an adaptive construction of a quantum state for the quantum-selected configuration interaction (QSCI) method. QSCI allows us to select important electronic configurations in the system to perform CI calculation (subspace diagonalization of the Hamiltonian) by sampling measurement for a proper input quantum state on a quantum computer, but how we prepare a desirable input state has remained a challenge. We propose an adaptive construction of the input state for QSCI in which we run QSCI repeatedly to grow the input state iteratively. We numerically illustrate that our method, dubbed ADAPT-QSCI, can yield accurate ground-state energies for small molecules, including a noisy situation for eight qubits where error rates of two-qubit gates and the measurement are both as large as 1%. ADAPT-QSCI serves as a promising method to take advantage of current noisy quantum devices and pushes forward its application to quantum chemistry.   

Quantum simulation of strongly correlated lattice systems using adaptive algorithms and operator tiling

Adaptive variational quantum simulation algorithms have been shown to be highly successful in finding the ground-state properties of small molecules, but their effectiveness and resource efficiency in the context of condensed matter systems has been studied less. We will present an adaptive algorithm to systematically prepare strongly correlated ground states of lattice Hamiltonians on quantum processors. Our approach utilizes ADAPT-VQE, which requires a user-defined operator pool from which trial wavefunctions are constructed dynamically during runtime. The efficiency of the algorithm depends critically on the choice of pool. We will describe a systematic method for constructing pools for problems with lattice structure called operator tiling, and we prove that such pools are capable of exactly representing the target wavefunction for any system size. We demonstrate the technique on the Heisenberg and Fermi-Hubbard models and establish its effectiveness in finding compact representations of the ground states.   

Towards Classical Descriptions of the Quantum Approximate Optimization Algorithm

We summarize and extend the concept of homogeneity in the Quantum Approximate Optimization Algorithm. Informally, homogeneity refers to an empirically-observed phenomenon that for QAOA on certain constraint satisfaction problems (CSPs) and parameter schedules, bitstrings (representing variable configurations) with identical cost retain similar amplitudes throughout the algorithm. Previous works assumed a more strong version of this phenomenon, where bitstrings with identical cost retain identical amplitudes, and leveraged this, along with problem class properties, to create polynomial-sized proxy for QAOA, and empirically studied how faithfully the proxy represents QAOA. Here, we aim to extend the model, incorporating deviations from homogeneity, with the goal of creating a "second-order" homogeneous proxy for QAOA, with the goal of capturing more qualities of QAOA, while retaining polynomial memory and time requirements.   

Adaptive Variational Quantum Dynamics Simulations with the TETRIS method

Adaptive variational quantum dynamics simulation (AVQDS) [1] has been developed as a near-term quantum algorithm to accurately simulate dynamical quantum systems using automatically generated unitaries that are more compressed than Trotterized circuits. Here we report an improved version of AVQDS by porting the Tiling Efficient Trial circuits with Rotations Implemented Simultaneously (TETRIS) technique [2], which adaptively adds layers of disjoint unitary gates to the ansatz to keep the McLachlan distance below a threshold. We apply TETRIS AVQDS to simulate the quench dynamics of local spin lattice models and demonstrate that it significantly reduces the quantum circuit depth and the number of 2-qubit operators. We also study the dynamical response of a BH molecule in an oscillating electric field and evaluate the first and second order polarizability, showing that TETRIS AVQDS can be applied to problems with a time-dependent Hamiltonians.

[1] Y.-X. Yao, N. Gomes, F. Zhang, T. Iadecola, C.-Z. Wang, K.-M. Ho, and P. P. Orth, Adaptive variational quantum dynamics simulations, Phys. Rev. X Quantum 2, 030307 (2021).

[2] P. G. Anastasiou, Y. Chen, N. J. Mayhall, E. Barnes, and S. E. Economou, Tetris-adapt-vqe: An adaptive algorithm that yields shallower, denser circuit ansätze, arXiv:2209.10562 (2022).   

Grover QAOA for 3-SAT: Quadratic Speedup, Fair Sampling, and Parameter Clustering

The Boolean satisfiability (SAT) problem, the first to be proven NP-complete, serves as a benchmark for quantum algorithms. We demonstrate a quadratic speedup over classical brute force search by the quantum approximate optimization algorithm (QAOA) with a Grover mixer for 3-SAT problems. In contrast to QAOA with the standard transverse field mixer, the Grover QAOA's samples all solutions uniformly, while in contrast to running the standard Grover search with an oracle implementing the 3-SAT instances, the Grover QAOA requires less quantum resources. These advantages come at the cost of requiring optimization of the variational parameters in the QAOA, but we find that simply assuming the angles are independent of the round of QAOA retains the speedup, and the optimal angles can easily be found. We find evidence for even further parameter clustering over different problem instances. These findings are corroborated through experiments up to 2 rounds of QAOA on the IonQ Aria quantum computer. Furthermore, the observed parameter clustering suggests the possibility of reducing the classical optimization overhead for QAOA.   

Parameter Setting in Quantum Approximate Optimization of Weighted Problems

Quantum Approximate Optimization Algorithm (QAOA) is a leading candidate algorithm for solving combinatorial optimization problems on quantum computers. However, in many cases QAOA requires computationally intensive parameter optimization. The challenge of parameter optimization is particularly acute in the case of weighted problems, for which the eigenvalues of the phase operator are non-integer and the QAOA energy landscape is not periodic. In this work, we develop parameter setting heuristics for QAOA applied to a general class of weighted problems. First, we derive optimal parameters for QAOA with depth p=1 applied to the weighted MaxCut problem under different assumptions on the weights. In particular, we rigorously prove the conventional wisdom that in the average case the first local optimum near zero gives globally-optimal QAOA parameters. Second, for p ≥ 1 we prove that the QAOA energy landscape for weighted MaxCut approaches that for the unweighted case under a simple rescaling of parameters. Hence, we can use parameters previously obtained for unweighted MaxCut for weighted problems. Finally, we prove that for p=1 the QAOA objective sharply concentrates around its expectation, which means that our parameter setting rules hold with high probability for a random weighted instance. We numerically validate this approach on general weighted graphs and show that on average the QAOA energy with the proposed fixed parameters is only 1.1 percentage points away from that with optimized parameters.   

Towards optimal circuit construction for the quantum approximate optimization algorithm

The quantum approximate optimization algorithm (QAOA) is used to approximately solve combinatorial optimization (CO) problems. In the algorithm, an operator known as the cost Hamiltonian $C$ is used to encode the details of the CO problem via quantum gates. The parameters of the algorithm are then optimized with respect to the expected value of $C$. In this work, we study how modifying the gate implementation aspect of $C$ (while calculating the expected value with the original $C$) can affect the output of QAOA. Specifically, we solve the MaxCut problem of a graph $G$ in with three types of changes to $C$: using a randomly generated $C$, using a random subgraph of $G$ to generate $C$, and a special case where we choose a subgraph of $G$ that has triangles removed. We derive an expected value formula using this modified $C$ and show numerically that in some cases this modification performs better than normal QAOA.   

A Distributional Approach to Quantum Approximate Optimization Algorithms

We describe a distributional approach to solving combinatoric optimization problems using quantum approximate optimization algorithms (QAOA). The framework of QAOA was developed for global optimization of combinatorial cost functions. However, in many problems of interest, families of solutions near the optima are needed to robustly solve problems in resource allocation, multiple target tracking, and multi-agent control. The single-point optimal allocation may be brittle to changing situations and unable to provide alternative solutions without a full ab initio re-analysis which may result in unacceptable time delay; some "slack" is desirable in practice. In our approach, we use QAOA to sample many different solutions to a combinatorial optimization problem that lie in a low energy band of the associated cost Hamiltonian. We view the repeated runs of QAOA as generating a probability mass function (PMF) on basis states, such that quantum measurement samples this PMF, and the full state is reconstructed tomographically. Central to our approach is identifying a distributional metric to optimize rather than a point estimator. Distributional metrics will be discussed as well as applications to Bayesian filtering and resource allocation problems.   

Direct observation of geometric phase interference in dynamics around a conical intersection with a trapped ion analog quantum simulator

Photochemical reactions that occur in molecular processes such as our vision often involve rapid and efficient reactions that occur on femtosecond timescales. However, simulating their dynamics can be challenging with conventional computers, particularly in strong vibronic (vibrational and electronic) coupling regimes where common approximations break down. We show that vibronic coupling Hamiltonians representing ultrafast molecular dynamics can be efficiently simulated on an analogue quantum simulator with coupled internal and bosonic states. We experimentally demonstrate our simulator by engineering a Jahn-Teller conical intersection (CI) in the internal and external degrees of freedom of a trapped ion [1]. We reconstruct the motional wavepacket’s probability density as it encircles the CI and observe clear interference due to geometric phase. Our experimental results validate the feasibility of using analogue quantum simulators with trapped ions to study ultrafast molecular dynamics.

[1] C. H. Valahu et al., Nature Chemistry (2023), 10.1038/s41557-023-01300-3