Session K49: Algorithms and Implementations on Near-Term Quantum Computers

Algorithms for quantum computing, communication networks, and metrology: a near-term perspective

Recent years have seen rapid progress in the development of quantum technologies, ranging from quantum computing to quantum repeaters to quantum sensors. At the same time, today's qubits are imperfect, leading to losses and errors that limit the use of these technologies. In the absence of full-scale, fault-tolerant quantum error correction, which can in principle overcome the limitations arising from noise and loss and allow us to achieve the ideal performance for our tasks of interest, to what extent can we circumvent these limitations, and thereby make the best possible use of our currently noisy, imperfect quantum devices? In other words, what is the best possible performance that can be achieved using today's noisy, imperfect quantum devices? In this talk, I present some of the progress that has been made on answering this question. I present recent work on devising algorithms and protocols (along with their performance analysis) for quantum computing, communication networks, and metrology, in the regime of limited and noisy qubits. Such a near-term analysis often necessitates diving deeper into the physics, and the use of new mathematical tools. I will in particular highlight how mathematical tools such as Markov chains and classical and quantum hypothesis testing have elucidated our understanding of algorithms for quantum error mitigation, quantum repeaters, and quantum metrology. While such analyses are at the outset tailored to the near-term regime of few and noisy qubits, it is expected that such a perspective will nevertheless better guide the development of quantum devices on the path towards quantum fault-tolerance.   

Near-term algorithms on a trapped-ion quantum computer

Recent technical improvements in trap fabrication, rapid ion loading, and signal broadcasting have enabled Quantinuum's H2 trapped-ion quantum computer, which brings the high fidelities, flexible connectivity, and mid-circuit measurement capabilities of the H1 system to a platform designed to accommodate more than 50 qubits. I will detail how H2's unique capabilities result in strong performance on a variety of near-term system-level algorithmic benchmarks, such as random circuit sampling, Hamiltonian simulation, and QAOA.   

NISQ Computing the Climate

Classical nonlinear dynamical systems can often be characterized by steady-state probability distribution functions (PDFs). PDFs can be obtained by accumulating statistics from simulation, or alternatively as a solution to the linear Fokker-Planck equation (FPE). Numerical solution of the FPE, however, becomes exponentially hard as the number of dimensions increase. We investigate the utility of Noisy Intermediate Scale Quantum (NISQ) devices as an alternative to classical computation. In particular, we employ the Quantum Phase Estimation (QPE), Variational Quantum Deflation, and Variational Quantum Singular Value Decomposition algorithms to obtain the steady-state statistics of the 3D Lorenz-63 chaotic dynamics using a dimensionally-reduced FPE operator [arXiv:2304.03362]. The same approach is used to investigate the Held-Suarez climate model. The algorithms are implemented on publicly available IBM hardware to test their efficacy. Furthermore, we demonstrate the efficacy of dynamical decoupling as a tool to mitigate errors within the QPE circuit.   

Qubit efficient quantum algorithms for the vehicle routing problem on NISQ processors

The vehicle routing problem with time windows (VRPTW) is a common optimization problem faced within the logistics industry. In this work, we explore the use of a previously-introduced qubit encoding scheme to reduce the number of qubits, to evaluate the effectiveness of NISQ devices when applied to industry relevant optimization problems. We apply a quantum variational approach to a testbed of multiple VRPTW instances ranging from 11 to 3964 routes. These intances were formulated as quadratic unconstrained binary optimization (QUBO) problems based on realistic shipping scenarios. We compare our results with standard binary-to-qubit mappings after executing on simulators as well as various quantum hardware platforms, including IBMQ, AWS (Rigetti), and IonQ. These results are benchmarked against the classical solver, Gurobi. Our approach can find approximate solutions to the VRPTW comparable to those obtained from quantum algorithms using the full encoding, despite the reduction in qubits required. These results suggest that using the encoding scheme to fit larger problem sizes into fewer qubits is a promising step in using NISQ devices to find approximate solutions for industry-based optimization problems, although additional resources are still required to eke out the performance from larger problem sizes.   

Extracting and evaluating performance of NISQ Optimization experiments: beyond angle-parameter setting

The NISQ (Noisy Intermediate-Scale Quantum) era was ushered in approximately 5 years ago, marking a period of experimentation with noisy quantum processors. It has been characterized by a global effort involving hundreds of small-scale experiments across various experimental platforms. These experiments have validated numerous noise models and have tested the practical aspects of quantum heuristics, including QAOA and its simple variants. Owing to advancements in hardware quality and control software, there have been several recent demonstrations of experimental runs on gate-model noisy quantum processors, showcasing the use of over 20 qubits in regimes where simulations become challenging. In this talk, we will discuss insights gained from the DARPA ONISQ program, where NASA, USRA, and Rigetti Computing employed an array of techniques to combat noise while aiming to solve non-trivial binary optimization problems. We will delve into the impacts of the discovered techniques, which encompass ansatz approximations, swap-network synthesis, over-parametrization, categorical parameters like ordering and symmetry transformations, and iterative decompositions. We will also explore how these can be amalgamated into a cohesive algorithm-tuning strategy that can be executed on the fly, achieving high approximation ratios within a few thousand runs for problems with 50+ variables.   

Variational quantum optimization with qubit-efficient encoding of problems

Variational quantum optimization algorithms show promise in solving hard combinatorial optimization problems, which could have significant impact on operational domains such as supply chains and logistics. However, their use is currently limited by the number of qubits on the existing hardware which have O(100) qubits, while heuristic classical algorithms can solve problems with O(1000) variables. We implement a qubit-efficient mapping of optimization problems that will enable larger problems to be mapped to currently available quantum computers. The qubit-efficient mapping uses a many-to-one map from classical variables to qubits, and stores the variables in an entangled wavefunction of fewer qubits. We quantify the performance of variational quantum circuits in solving Ising spin glass problems up to 1000 variables, and investigate the tradeoff between algorithm performance and the qubit-efficiency of the encoding. The qubit-efficient mapping brings quantum algorithms into competition with classical heuristic algorithms in the problem sizes investigated.   

Design and execution of quantum circuits using tens of superconducting qubits and thousands of gates for dense Ising optimization problems

We develop a hardware-efficient ansatz for variational optimization, derived from existing ansätze in the literature, that parametrizes subsets of all interactions in the cost hamiltonian in each layer. We treat gate orderings as a variational parameter and observe that doing so can provide significant performance boosts in experiments. We carried out experimental runs of a compilation-optimized implementation of fully-connected Sherrington-Kirkpatrick Hamiltonians on a 50-qubit linear-chain subsystem of Rigetti's Aspen-M-3 transmon processor. Our results indicate that, for the best circuit designs tested, the average performance at optimized angles and gate ordering parameters increases with circuit depth (using more parameters), despite the presence of a high level of noise. We report performance significantly better than using a random guess oracle for circuits involving up to ~5,000 two-qubit and ~5,000 one-qubit native gates. We additionally discuss various takeaways from our results toward more effective utilization of current and future quantum processors for optimization. The submission is based on preprint arXiv:2308.12423.   

Efficient Implementation of the Fermionic Schrodinger Equation with Adiabatic Quantum Computation

One obvious goal of quantum computing that dates back to its inception is to solve for the ground state of the Schrödinger equation.   The problem addressed here is the first quantization description of a position space multi-particle multi-dimensional Schrödinger equation on a periodic lattice where the particles are identical fermions.  

The objective is to maintain an exponential advantage over classical computing. In Chang, McElvain, Rrapaj, Wu, PRX Quantum 3(2), 020356,

the authors present a solution for distinguishable particles.  The work described in this talk is found in arXiv:2309.08101.

I associate a specific encoding for each anti-symmetric multi-particle state.  The encoding depends on an ordering of the particles according to their position in the multi-dimensional space.    Fermion exchange symmetry complicates the description of derivative operators like the Laplacian because the motion of a fermion to a neighboring lattice position in two or more dimensions can change the ordering the encoding depends on.  The key to success is that it is possible to bound the the circuit size required to restore the proper ordering. 

The key result is that the number of qubits and circuit size for the Laplacian scale logarithmically with the number of position states and linearly with the number of particles.   

Incompressible flow simulation via a hybrid quantum-classical approach and variational algorithm

Partial differential equation (PDE) solvers for Navier-Stokes fluids problems are important for many science and engineering problems. Quantum algorithms have been verified to solve linear PDEs and verified on simulators. Fault-tolerant quantum hardware may make exponential speedups possible, for example, via linearization methods and HHL-type linear solvers. Still, NISQ-era near-term quantum hardware requires algorithms that demand less quantum volume: shallower gate depths and fewer qubits. Variational algorithms, like VQE and VQLS, are appropriate under such restrictions. Here, we present work on a hybrid approach to solving the nonlinear incompressible Navier-Stokes equations. A classical computer performs the nonlinear computations, and a quantum algorithm, on simulator or hardware, performs the cumbersome Poisson equation solve that enforces mass continuity. A lid-driven cavity problem is investigated at various Reynolds numbers and grid resolutions to determine the sensitivity of the global and local Poisson equation to the variation algorithm and quantum noise.   

Energy-filtered random-phase states as microcanonical thermal pure quantum states

We propose a method to calculate finite-temperature properties of many-body systems for microcanonical ensembles, which may find a potential application of near-term quantum computers. In our formalism, a microcanonical ensemble is specified with a target energy and a width of the energy window, by expressing the density of states as a sum of Gaussians centered at the target energy with its spread associated with the width of the energy window. Using the Fourier representation of the Gaussian, we then show that thermodynamic quantities such as entropy and temperature can be calculated by evaluating the trace of the time-evolution operator, and the trace of the time-evolution operator multiplied by the Hamiltonian of the system. We also describe how these traces can be evaluated using random diagonal-unitary circuits suitable for quantum computation. We demonstrate the proposed method by numerically calculating thermodynamic quantities of the one-dimensional spin-1/2 Heisenberg model on small clusters and show that the proposed method is most effective for the target energy around which a larger number of energy eigenstates exist.   

A Graphical Language for Computer-aided Design and Synthesis of Quantum Algorithms

Both the tasks of quantum algorithm design and that of digital logic circuit design are constrained optimization problems. In both, the level of complexity can quickly become overwhelming. Tackling this complexity problem can be purely text-based, as is done with Hardware Description Languages (Verilog, VHDL), but graphical interfaces are highly effective in empowering developers, introducing intuition by abstraction. A graphical approach can be flexible enough to present different levels of detail as needed by the designer and expressive enough for a succinct description of all pertinent features.

In this work, we present an interface for the graphical automated design of quantum algorithms inspired by Electronic Design Automation (EDA) tools, which have been the workhorse of digital logic design for decades. 

The graphical language and interface we introduce are integrated with Classiq’s quantum circuit synthesis engine [1,2], thus fully automating the design process. Using this tool, we demonstrate the synthesis of a Shor’s algorithm circuit involving 22 qubits and composed of more than 10^4 individual gate operations. 

While built on modern web technologies, the tool draws inspiration from and extends traditional methods. The laws of quantum mechanics prohibit some classical EDA techniques. For example, the no-cloning theorem prohibits an element from being connected to multiple output elements (an operation known as fan-out in digital logic design). The system respects these limitations and, in addition, supports idiosyncratic patterns that appear specifically in quantum circuits. This system is extensible and is planned to support hybrid modes of execution in future releases.   

[1] US-11294797-B1  Debugger for quantum computers Naveh; Amir et al.2022-04-05288

[2] US-11288589-B1  Quantum circuit modeling Naveh; Yehuda et al.2022-03-2914   

Resource estimation of Fault Tolerant algorithms using Qᴜᴀʟᴛʀᴀɴ

Understanding the constant factors for fault tolerant algorithms is imperative to quantify the utility of quantum computation and will ultimately drive substantial algorithmic improvements. Quantum algorithm researchers are writing long (50-100 page) papers describing quantum algorithms and performing resource estimation, using pages and pages of text. To accelerate this important work, we've released QUALTRAN - an open sourced Python library for expressing and analyzing Fault Tolerant quantum algorithms. In this talk, we will give an overvew of the high level features of our software package and demonstrate it's utility by presenting end to end resource estimation of a number of different state-of-the-art fault tolerant quantum algorithms.   

Improved phase factor determination in quantum signal processing

Quantum Signal Processing (QSP) provides a framework for implementing polynomial functions of non-unitary matrices on quantum computers. However, determining the set of parameters, known as phase factors, needed to implement a particular polynomial can be challenging from a classical pre-processing perspective. The recently-proposed Generalized Quantum Signal Processing (GQSP) framework provides an efficient algorithm for finding these parameters (at the level of GQSP). Based on a correspondence between QSP and GQSP, we discuss improvements to the determination of QSP phase factors.