From Ansätze to Z-Gates: A NASA View of Quantum Computing

Eleanor Rieffel, Stuart Hadfield, Tad Hogg, Salvatore Mandrà, Jeffrey Marshall, Gianni Mossi, Bryan O’Gorman, Eugeniu Plamadeala, Norm M. Tubman, Davide Venturelli, Walter Vinci, Zhihui Wang, Max Wilson, Filip Wudarski, Rupak BiswasAdvances 2019 · DOI · arXiv · OpenAlex

TL;DR

NASA’s Quantum Artificial Intelligence Laboratory (QuAIL) provides a high-level roadmap for navigating the "NISQ" (Noisy Intermediate-Scale Quantum) era. Their core contribution is a suite of algorithms and tools—most notably the Quantum Alternating Operator Ansatz—designed to map complex, constrained NASA mission problems (like scheduling and material science) onto early, imperfect quantum hardware.

What Problem Does This Paper Address?

We are currently in the NISQ era: we have quantum computers with 50–100 qubits, but they are too noisy for full error correction and too small for famous algorithms like Shor’s (which breaks encryption). The challenge is finding "useful quantum supremacy"—tasks where these early machines can outperform supercomputers on practical problems.

NASA faces massive combinatorial challenges in planning, fault diagnosis, and satellite communications. This paper addresses how to bridge the gap between abstract quantum theory and the messy reality of current hardware constraints, such as limited qubit connectivity and high error rates.

Methods

The paper surveys several novel algorithmic and architectural approaches:

  • Quantum Alternating Operator Ansatz (QAOA): An extension of the standard Quantum Approximate Optimization Algorithm. While the original QAOA struggles with "hard constraints" (rules that cannot be broken), NASA’s version uses specialized "mixing operators" that keep the quantum state within a "feasible subspace." This ensures the computer only explores valid solutions (e.g., a satellite cannot be in two places at once).
  • Temporal Planning for Compilation: To run a quantum program, logical gates must be mapped to physical qubits. NASA uses automated "temporal planning" (a classical AI technique) to find the most efficient way to move information around the chip, minimizing the "makespan" (total execution time) to beat decoherence.
  • qFlex Simulator: A high-performance classical simulator that uses tensor network contraction to mimic quantum circuits. This allows researchers to verify quantum results and establish a baseline for "quantum supremacy."
  • Quantum-Assisted Machine Learning: The authors integrate quantum annealers into Generative Adversarial Networks (GANs) and Variational Autoencoders (VAEs), using the quantum hardware to sample from complex probability distributions that are difficult for classical computers.

Datasets

The researchers evaluated their hybrid quantum-classical models using:

  • Standard ML Benchmarks: MNIST (handwritten digits), CIFAR-10, and LSUN (bedroom images).
  • Combinatorial Benchmarks: MaxCut on "ring of disagrees" graphs, Maximum Independent Set, and Traveling Salesperson problems.
  • NASA-Specific Models: Aeronautic communication network models and "FeMoco" (a complex molecule involved in nitrogen fixation) for chemistry simulations.

Key Insights and Ideas

  • The "Feasible Subspace" is Key: For real-world optimization, most possible bit-strings are invalid solutions. By designing quantum operators that physically cannot leave the valid solution space, the algorithm converges much faster.
  • The Power of the Pause: In quantum annealing, simply "pausing" the process at a specific moment (near the minimum energy gap) allows the system to thermalize, significantly increasing the probability of finding the correct answer.
  • Classical Simulation is a Moving Target: The paper highlights that "quantum supremacy" isn't a fixed finish line. As quantum hardware improves, NASA’s classical simulation team (using the Pleiades and Electra supercomputers) develops better algorithms to keep up, pushing quantum researchers to innovate further.
  • Physics-Inspired Heuristics: Even if a quantum speedup isn't found immediately, the attempt to write quantum algorithms often leads to "quantum-inspired" classical algorithms that outperform previous state-of-the-art methods.

Key Results

  • Simulation Scale: Using the qFlex simulator on NASA supercomputers, the team successfully simulated 72-qubit circuits (like Google’s Bristlecone) at depths previously thought to be at the edge of classical reach.
  • HPC Benchmarking: They achieved a peak performance of 281 Pflop/s on the Summit supercomputer for quantum circuit simulations, representing 92% of the machine's maximum achievable performance.
  • Annealing Advantages: In specific hard optimization problems, the D-Wave 2000Q quantum annealer showed a better "pre-factor" (constant time overhead) than state-of-the-art classical heuristics, even if the scaling remained similar.

Limitations and Future Work

  • The Parameter Problem: Finding the optimal "angles" ($\beta, \gamma$) for QAOA is itself an NP-hard classical optimization problem. The authors note that "barren plateaus" (areas where the gradient disappears) make this search difficult.
  • Connectivity Constraints: Most NISQ algorithms assume qubits can talk to any other qubit, but real hardware is usually a 2D grid. Future work focuses on "swap networks" to mitigate this.
  • Scaling to Mission-Size: While the "toy" problems (like MaxCut on a ring) are understood, the transition to application-scale NASA missions (like global satellite scheduling) requires hardware with lower noise and higher qubit counts than currently available.

Summary updated

Abstract

For the last few years, the NASA Quantum Artificial Intelligence Laboratory (QuAIL) has been performing research to assess the potential impact of quantum computers on challenging computational problems relevant to future NASA missions. A key aspect of this research is devising methods to most effectively utilize emerging quantum computing hardware. Research questions include what experiments on early quantum hardware would give the most insight into the potential impact of quantum computing, the design of algorithms to explore on such hardware, and the development of tools to minimize the quantum resource requirements. We survey work relevant to these questions, with a particular emphasis on our recent work in quantum algorithms and applications, in elucidating mechanisms of quantum mechanics and their uses for quantum computational purposes, and in simulation, compilation, and physics-inspired classical algorithms. To our early application thrusts in planning and scheduling, fault diagnosis, and machine learning, we add thrusts related to robustness of communication networks and the simulation of many-body systems for material science and chemistry. We provide a brief update on quantum annealing work, but concentrate on gate-model quantum computing research advances within the last couple of years.
BibTeX
@inproceedings{rieffel2019from,
  author = {Eleanor Rieffel and Stuart Hadfield and Tad Hogg and Salvatore Mandrà and Jeffrey Marshall and Gianni Mossi and Bryan O’Gorman and Eugeniu Plamadeala and Norm M. Tubman and Davide Venturelli and Walter Vinci and Zhihui Wang and Max Wilson and Filip Wudarski and Rupak Biswas},
  title = {{From Ansätze to Z-Gates: A NASA View of Quantum Computing}},
  booktitle = {Advances},
  year = {2019},
  doi = {10.3233/apc190010},
}

Loading related content...

Figure