Bulletin of the American Physical Society
2023 APS March Meeting
Volume 68, Number 3
Las Vegas, Nevada (March 510)
Virtual (March 2022); Time Zone: Pacific Time
Session D64: Quantum Simulation I: Speedups, Improvements, and BeyondFocus

Hide Abstracts 
Sponsoring Units: DQI Chair: Brian Neyenhuis, Quantinuum Room: Room 415 
Monday, March 6, 2023 3:00PM  3:12PM 
D64.00001: Interpolation of Trotter data for eigenvalue and expectation value estimation Gumaro Rendon, Nathan Wiebe, Jacob A Watkins In this work, we provide a paradigmshifting 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 Trotterstep 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 postprocessing costs. We also compare the error propagation on the interpolant using hard bounds (confidence intervals) coming typically from semiclassical 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 superexponentially 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. 
Monday, March 6, 2023 3:12PM  3:24PM 
D64.00002: Efficient calculation of nuclear forces on noisy intermediatescale quantum computers Michael Streif, Thomas E O'Brien, Nicholas C Rubin, Raffaele Santagati, Yuan Su, William J Huggins, Joshua Goings, Nikolaj Moll, Elica Kyoseva, Matthias Degroote, Christofer Tautermann, Joonho Lee, Dominic W Berry, Nathan Wiebe, Ryan Babbush Accurate nuclear forces are required to simulate the movement of atoms and molecules over time, an essential computational tool for drug discovery. 
Monday, March 6, 2023 3:24PM  3:36PM 
D64.00003: Efficient simulation of materials on faulttolerant quantum computers using translational symmetries Nicholas C Rubin 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 kpoints 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. 
Monday, March 6, 2023 3:36PM  4:12PM 
D64.00004: Quantum Speedups for Computing Expectation Values and Partition Functions Invited Speaker: Yassine Hamoudi 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. 
Monday, March 6, 2023 4:12PM  4:24PM 
D64.00005: Universal Quantum Speedup for BranchandBound, BranchandCut, and TreeSearch Algorithms Shouvanik Chakrabarti, Pierre Minssen, Romina Yalovetzky, Marco Pistoia Mixed Integer Programs (MIPs) model many optimization problems of interest in Computer Science, Operations Research, and Financial Engineering. Solving MIPs is NPHard in general, but commercial solvers often find nearoptimal solutions for problems of intermediate size. Modern MIP solvers use BranchandCut algorithms, which combine BranchandBound logic with cuttingplane routines. Montanaro proposed a quantum algorithm with a nearquadratic speedup compared to classical BranchandBound algorithms in the worst case, when every optimal solution is desired. In practice, however, a nearoptimal solution is satisfactory, and by leveraging treesearch heuristics to search only a portion of the solution tree, classical algorithms can perform much better than the worstcase guarantee. We propose a quantum algorithm with universal nearquadratic speedup over classical BranchandBound algorithms for every input, i.e., if classical BranchandBound 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 depthbased, costbased, and A∗ heuristics. Universal speedups are also obtained for BranchandCut 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. 
Monday, March 6, 2023 4:24PM  4:36PM 
D64.00006: Perturbation theory with quantum signal processing Kosuke Mitarai, Wataru Mizukami 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 faulttolerant quantum computers. 
Monday, March 6, 2023 4:36PM  4:48PM 
D64.00007: Realtime quantum Krylov subspace algorithms with stochastic compilation and double factorization Cristian L Cortes, Nicholas H Stair, jeffrey cohn, Mario Motta, Robert M Parrish Realtime quantum Krylov diagonalization algorithms provide a lowcost alternative to standard quantum phase estimation algorithms for ground and excitedstate energy estimation. While deterministic TrotterSuzuki methods are typically used to compile the time evolution operator in such algorithms, the necessary gate depths are prohibitively large for the simulation of largescale systems on nearterm 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 lowrank 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 circuitbased 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 TrotterSuzuki decompositions. 
Monday, March 6, 2023 4:48PM  5:00PM 
D64.00008: On proving the robustness of algorithms for early faulttolerant quantum computers Peter D Johnson, Amara Katabarwa, Rutuja Kshirsagar The hope of the quantum computing field is that quantum architectures are able to scale up and realize faulttolerant 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 faulttolerant quantum computing. Costly error correction might warrant settling for errorprone 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. 
Monday, March 6, 2023 5:00PM  5:12PM 
D64.00009: Lyapunov controlinspired quantum algorithms for ground state preparation James B Larsen, Andrew D Baczewski, Matthew D Grace, Alicia B Magann The Feedbackbased 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 feedbackbased quantum algorithms for preparing ground states of quantum systems in a manner that is optimizationfree. We investigate its performance for finding ground states of the FermiHubbard 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. SAND202214643 A. 
Monday, March 6, 2023 5:12PM  5:24PM 
D64.00010: Modeling Quantum Algorithm Performance on Early FaultTolerant Quantum Computers Qiyao Liang, Yiqing Zhou, Archismita Dalal, Peter D Johnson Will quantum computing become useful in the early faulttolerant era (EFTQC)? 
Monday, March 6, 2023 5:24PM  5:36PM 
D64.00011: Variational optimization of PREPARE circuit for blockencoding Hamiltonians without ancillary qubits Hayata Morisaki, Keisuke Fujii, Kosuke Mitarai, Yuya O Nakagawa In the stateoftheart quantum phase estimation algorithms, a quantum state, whose amplitudes correspond to the coefficients of the Hamiltonian, needs to be prepared to blockencode the Hamiltonian. While this preparation process can be done with T gates scaling linearly to the number of coefficients by using quantum readonly 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 twoqubit quantum gates in an optimal way. To evaluate the performance of the proposed method, we decompose the generated PREPAREcircuit 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 hardwareefficient quantum phase estimation algorithm. 
Monday, March 6, 2023 5:36PM  5:48PM 
D64.00012: An adaptive quantumphaseestimation protocol for NISQ hardware Joseph G Smith, David R ArvidssonShukur, Crispin H Barnes Given N_{tot} applications of a unitary operation with an unknown phase, a phaseestimation protocol based on a largescale faulttolerant 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 nearterm quantum devices, noiseless entanglementfree protocols have been developed, achieving a Ο(log N_{tot} / N_{tot}) meanabsoluteerror scaling. Here, we propose an adaptive Bayesian protocol for nearterm 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 quantumphase estimation algorithm for realistic values of N_{tot}. 
Monday, March 6, 2023 5:48PM  6:00PM 
D64.00013: Preparing thermal states on noiseless and noisy programmable quantum processors Ramis Movassagh, Oles Shtanko Nature is governed by precise physical laws, which can inspire the discovery of new computerrun 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 hightemperature 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 (nearterm) 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 nearterm quantum devices. To illustrate, we simulate the thermal state of the spinless FermiHubbard model on the latest generation of available quantum computers. 
Follow Us 
Engage
Become an APS Member 
My APS
Renew Membership 
Information for 
About APSThe American Physical Society (APS) is a nonprofit membership organization working to advance the knowledge of physics. 
© 2024 American Physical Society
 All rights reserved  Terms of Use
 Contact Us
Headquarters
1 Physics Ellipse, College Park, MD 207403844
(301) 2093200
Editorial Office
100 Motor Pkwy, Suite 110, Hauppauge, NY 11788
(631) 5914000
Office of Public Affairs
529 14th St NW, Suite 1050, Washington, D.C. 200452001
(202) 6628700