Session D64: Quantum Simulation I: Speedups, Improvements, and Beyond

Interpolation of Trotter data for eigenvalue and expectation value estimation

In this work, we provide a paradigm-shifting approach in which we achieve a Õ(log 1/ε) cost scaling when estimating observables with a single ancillary qubit, where ε is the error on the observable from approximating the Hamiltonian dynamics. This method relies on interpolating the observable estimated where Hamiltonian dynamics are simulated at different Trotter-step sizes. With these methods, we avoid having to simulate the Hamiltonian evolution with high precision in situ which incurs in extra quantum cost and qubits. Instead, we choose to trade those quantum costs for similar classical post-processing costs. We also compare the error propagation on the interpolant using hard bounds (confidence intervals) coming typically from semi-classical phase estimation, or IQAE, and also a probabilistic approach using Gaussian quantum phase estimation. We demonstrate that using the probabilistic approach has an improved cost scaling, for which a confidence interval can also be obtained after interpolation is done, with a super-exponentially decaying error rate as you increase the interval. Numerical tests of the probabilistic approach are provided using the transverse Ising model with a size of two sities.   

Efficient calculation of nuclear forces on noisy intermediate-scale quantum computers

Accurate nuclear forces are required to simulate the movement of atoms and molecules over time, an essential computational tool for drug discovery. 

However, most current quantum computing algorithms only focus on determining an accurate estimate of the ground state energy. In contrast to the ground state problem, calculating the nuclear forces of N_a atoms requires to estimate 3N_a expectation values of operators which do not commute with the Hamiltonian. 

In this talk, we show how to use noisy intermediate-scale quantum (NISQ) computers to extract nuclear forces and optimize the number of required samples from the quantum computer by using basis rotation groupings, importance sampling and fermionic shadows. We perform numerical simulations on hydrogen chains and water clusters, compare our findings to the cost of measuring the ground state energy and discuss the consequences of our results for quantum-enhanced molecular dynamics simulations.   

Efficient simulation of materials on fault-tolerant quantum computers using translational symmetries

Here we extend the infrastructure recently used in fault tolerant simulation of molecules to material systems defined over Bloch orbitals in second quantization. We demonstrate how to construct qubitized phase estimation oracles using various block encodings that take advantage of translational symmetry leading to a savings inversely proportional to the number of k-points sampled. We highlight this savings through a comparison to generic supercell simulations leveraging unmodified molecular algorithms for various simple systems and a Lithium Nickel Oxide battery cathode material. To identify potential quantum simulation advantage we compared quantum runtimes as a function of accuracy to flagship electronic structure simulations of the Lithium Nickel Oxide cathode material and other strongly correlated systems.    

Quantum Speedups for Computing Expectation Values and Partition Functions

Monte Carlo methods are used extensively in various fields of science and engineering, such as statistical physics, finance, or machine learning. At the core of these methods, one can often find Monte Carlo processes whose expected outcomes are to be estimated with the highest possible accuracy. Quantum computing has opened the path to new algorithmic primitives (for instance, Quantum Phase Estimation) that can provide noticeable advantages for estimating certain parameters. In this talk, we present new advanced quantum algorithms for estimating fundamental statistics such as the mean of multivariate distributions or the partition function of Gibbs distributions. We highlight the core techniques behind these results, and we describe directions for future work.   

Universal Quantum Speedup for Branch-and-Bound, Branch-and-Cut, and Tree-Search Algorithms

Mixed Integer Programs (MIPs) model many optimization problems of interest in Computer Science, Operations Research, and Financial Engineering. Solving MIPs is NP-Hard in general, but commercial solvers often find near-optimal solutions for problems of intermediate size. Modern MIP solvers use Branch-and-Cut algorithms, which combine Branch-and-Bound logic with cutting-plane routines. Montanaro proposed a quantum algorithm with a near-quadratic speedup compared to classical Branch-and-Bound algorithms in the worst case, when every optimal solution is desired. In practice, however, a near-optimal solution is satisfactory, and by leveraging tree-search heuristics to search only a portion of the solution tree, classical algorithms can perform much better than the worst-case guarantee. We propose a quantum algorithm with universal near-quadratic speedup over classical Branch-and-Bound algorithms for every input, i.e., if classical Branch-and-Bound has complexity Q on a given instance, our algorithm offers the same guarantees with a complexity of about √Q. Our results are valid for a wide variety of search heuristics, including depth-based, cost-based, and A∗ heuristics. Universal speedups are also obtained for Branch-and-Cut as well as heuristic tree search. Our algorithms are directly comparable to commercial MIP solvers such as Gurobi and CPLEX, and guarantee near quadratic speedup for a wide range of optimization problems.   

Perturbation theory with quantum signal processing

Perturbation theory is an important technique for reducing computational cost and providing physical insights in simulating quantum systems with classical computers. Here, we provide a quantum algorithm to obtain perturbative energies using quantum signal processing (QSP). The benefit of using quantum computers is that we can start the perturbation from a Hamiltonian that is classically hard to solve. Along with the perturbation theory, we construct a technique for ground state preparation with detailed computational cost analysis. We also estimate a rough computational cost of the algorithm for simple chemical systems such as water clusters and polyacene molecules. Unfortunately, we find that the proposed algorithm, at least in its current form, does not exhibit practical numbers despite of the efficiency of QSP compared to conventional quantum algorithms. However, perturbation theory itself is an attractive direction to explore because of its physical interpretability; it provides us insights about what interaction gives an important contribution to the properties of systems. This is in sharp contrast to the conventional approaches based on the quantum phase estimation algorithm, where we can only obtain values of energy. From this aspect, this work is a first step towards ``explainable'' quantum simulation on fault-tolerant quantum computers.   

Real-time quantum Krylov subspace algorithms with stochastic compilation and double factorization

Real-time quantum Krylov diagonalization algorithms provide a low-cost alternative to standard quantum phase estimation algorithms for ground and excited-state energy estimation. While deterministic Trotter-Suzuki methods are typically used to compile the time evolution operator in such algorithms, the necessary gate depths are prohibitively large for the simulation of large-scale systems on near-term devices. In this talk, I will discuss our recent work which introduces a new class of randomized quantum Krylov diagonalization (rQKD) algorithms which uses a combination of stochastic compilations strategies inspired by qDRIFT as well as low-rank double factorized Hamiltonian encoding strategies resulting in circuit depths with modest quantum resource requirements. To demonstrate the potential of the proposed rQKD algorithms, we provide numerical benchmarks for a variety of molecular systems with circuit-based statevector simulators achieving ground state energy errors of less than 1 kcal/mol with circuit depths orders of magnitude shallower than those required for deterministic Trotter-Suzuki decompositions.   

On proving the robustness of algorithms for early fault-tolerant quantum computers

The hope of the quantum computing field is that quantum architectures are able to scale up and realize fault-tolerant quantum computing. Due to engineering challenges, such "cheap" error correction may be decades away. In the meantime, we anticipate an era of "costly" error correction, or early fault-tolerant quantum computing. Costly error correction might warrant settling for error-prone quantum computations. This motivates the development of quantum algorithms which are robust to some degree of error as well as methods to analyze their performance in the presence of error. We introduce a randomized algorithm for the task of phase estimation and give an analysis of its performance under two simple noise models. In both cases the analysis leads to a noise threshold, below which arbitrarily high accuracy can be achieved by increasing the number of samples used in the algorithm. As an application of this general analysis, we compute the maximum ratio of the largest circuit depth and the dephasing scale such that performance guarantees hold. We calculate that the randomized algorithm can succeed with arbitrarily high probability as long as the required circuit depth is less than 0.916 times the dephasing scale.   

Lyapunov control-inspired quantum algorithms for ground state preparation

The Feedback-based Algorithm for Quantum OptimizatioN (FALQON) was recently proposed as a strategy for performing combinatorial optimization on quantum computers.?The key feature of this approach is that it?does not?require any classical optimization, which differentiates it from QAOA and other variational quantum algorithms. Instead, quantum circuit parameter values are set using a deterministic feedback law derived from quantum Lyapunov control principles. This feedback law guarantees a monotonic improvement in solution quality with respect to the depth of the quantum circuit. In this talk, we discuss how this framework can be adapted to applications beyond combinatorial optimization. To this end, we introduce a generalized formulation of feedback-based quantum algorithms for preparing ground states of quantum systems in a manner that is optimization-free. We investigate its performance for finding ground states of the Fermi-Hubbard model for strongly correlated quantum systems, and present a variety of numerical analyses exploring its robustness and convergence properties, the effect of parameter variation, and the impact of different modifications to the standard FALQON approach. Sandia National Labs is managed and operated by NTESS under DOE NNSA contract DENA0003525. SAND2022-14643 A.   

Modeling Quantum Algorithm Performance on Early Fault-Tolerant Quantum Computers

Will quantum computing become useful in the early fault-tolerant era (EFTQC)?

To answer this question, we must have accurate models of such quantum computers and of algorithm performance. In the EFTQC regime, qubits will be noisy, and quantum error correction will be expensive. Hence, it is also important to analyze the cost of quantum error correction needed to achieve a certain level of performance on the quantum computer.

Toward these goals, we develop a modularized framework to model the circuit-level noise, the algorithmic noise, the algorithm success probability, and the links between them. Specifically, we apply our framework to study the performance of a phase estimation algorithm. We analyze the error correction cost for this algorithm as a function of the target error rate, physical error rate, and error-correcting code properties. Our work lays the foundation for assessing the interplay between hardware and algorithmic performances in the early fault-tolerant era and beyond.   

Variational optimization of PREPARE circuit for block-encoding Hamiltonians without ancillary qubits

In the state-of-the-art quantum phase estimation algorithms, a quantum state, whose amplitudes correspond to the coefficients of the Hamiltonian, needs to be prepared to block-encode the Hamiltonian. While this preparation process can be done with T gates scaling linearly to the number of coefficients by using quantum read-only memory(QROM), it requires a large number of ancilla qubits. Here we propose a method to construct a quantum circuit to prepare an arbitrary quantum state without using any additional ancilla qubit. Specifically, we construct a PREPARE circuit with a small number of T gates by using automatic quantum circuit encoding (AQCE)[arXiv:2112.14524], which is a method to encode a given arbitrarily quantum state with a finite number of two-qubit quantum gates in an optimal way. To evaluate the performance of the proposed method, we decompose the generated PREPARE-circuit into Clifford+T gate set and estimated the number of T gates required to achieve chemical accuracy. As a result, the number of T gates is significantly reduced compared with a method that exactly prepares the quantum state without using ancilla qubits. The number of logical qubits is reduced to less than half compared to the preparation process by using QROM. Since the number of available logical qubits is expected to be limited in an early stage of FTQC, the proposed method without ancilla qubits and with smaller T gates is promising to construct a hardware-efficient quantum phase estimation algorithm.   

An adaptive quantum-phase-estimation protocol for NISQ hardware

Given N_tot applications of a unitary operation with an unknown phase, a phase-estimation protocol based on a large-scale fault-tolerant quantum system can reduce the standard deviation of an estimate of the phase from scaling like Ο(1/√N_tot) to scaling like Ο(1/N_tot). Due to the limited resources available to near-term quantum devices, noiseless entanglement-free protocols have been developed, achieving a Ο(log N_tot / N_tot)  mean-absolute-error scaling. Here, we propose an adaptive Bayesian protocol for near-term phase estimation, which shows high performance in the presence of noise. Our protocol’s mean absolute error scales as Ο(√(log(log N_tot)) / N_tot) in the noiseless limit and achieves the theoretically optimal scaling when noise is considered. Furthermore, we demonstrate that our protocol can outperform the asymptotically optimal quantum-phase estimation algorithm for realistic values of N_tot.   

Preparing thermal states on noiseless and noisy programmable quantum processors

Nature is governed by precise physical laws, which can inspire the discovery of new computer-run simulation algorithms. Thermal (Gibbs) states are the most ubiquitous for they are the equilibrium states of matter. Simulating thermal states of quantum matter has applications ranging from quantum machine learning to better understanding of high-temperature superconductivity and quantum chemistry. The computational complexity of this task is hopelessly hard for classical computers . The existing quantum algorithms either require quantum phase estimation rendering them impractical for current noisy hardware, or are variational which face obstacles such as initialization, barren plateaus, and a general lack of provable guarantee. We provide two quantum algorithms with provable guarantees to prepare thermal states on (near-term) quantum computers that avoid these drawbacks. The first algorithm is inspired by the natural thermalization process where the ancilla qubits act as the infinite thermal bath. This algorithm can potentially run in polynomial time to sample thermal distributions of ergodic systems-- the vast class of physical systems that equilibrate in isolation with respect to local observables. The second algorithm works for any system and in general runs in exponential time. However, it requires significantly smaller quantum resources than previous such algorithms. In addition, we provide an error mitigation technique for both algorithms to fight back decoherence, which enables us to run our algorithms on the near-term quantum devices. To illustrate, we simulate the thermal state of the spinless Fermi-Hubbard model on the latest generation of available quantum computers.