Quantum-classical tradeoffs and multi-controlled quantum gate decompositions in variational algorithms

Teague Tomesh, Nicholas B. Allen, Zain H. Saleem, Saleem, ZainarXiv 2022 · DOI · arXiv

TL;DR

This paper investigates how to optimize hybrid variational algorithms by balancing classical and quantum resources, specifically focusing on the Maximum Independent Set (MIS) problem. The authors demonstrate that using more sophisticated algorithmic variants (like DQVA) and specialized hardware features (like native Toffoli gates or qutrits) can drastically reduce the "gate decomposition cost," making complex quantum optimizations more feasible on today’s noisy hardware.

What Problem Does This Paper Address?

We are currently in the Noisy Intermediate-Scale Quantum (NISQ) era. Quantum computers are limited by two main factors: they have very few qubits, and the "gates" (operations) we perform on them are prone to errors.

Many interesting problems, like the Maximum Independent Set (MIS)—finding the largest group of nodes in a graph where no two are connected—are "constrained." To solve these on a quantum computer using the Quantum Approximate Optimization Algorithm (QAOA), we often need "multi-controlled" gates. These are complex operations where one qubit changes state only if several others are in a specific configuration.

The problem is that real hardware doesn't support these complex gates natively. We have to "decompose" them into a long string of simple one- and two-qubit gates. This process creates very "deep" (long) circuits that are often too noisy to produce useful results. The authors ask: How can we trade off classical computing power to shorten these quantum circuits, and what hardware improvements (like better native gates) would help the most?

Methods

The researchers compared three "flavors" of QAOA that offer different algorithmic tradeoffs:

  1. Single-Angle (SA-QAOA): The standard version; simple but requires deeper circuits.
  2. Multi-Angle (MA-QAOA): Uses more classical parameters to potentially achieve better results with shorter circuits.
  3. Dynamic Quantum Variational Ansatz (DQVA): A newer approach that uses a tunable number of parameters and multiple rounds of classical optimization to keep the quantum circuit as slim as possible.

On the hardware side, they analyzed how multi-controlled gates decompose into three different "native" gate sets:

  • $S^2_2$: Standard single- and two-qubit gates (like CNOT).
  • $S^2_3$: Includes a native three-qubit Toffoli gate.
  • $S^3_2$: Uses qutrits (three-level systems) instead of qubits, allowing for more efficient information storage during operations.

Finally, they introduced a new metric, Gate Decomposition Cost (GDC), which combines the number of gates needed with their expected fidelities (accuracy) into a single score to compare different hardware backends.

Datasets

The authors evaluated their approaches using:

  • 20-node benchmark graphs: Specifically 3-regular graphs and Erdös-Rényi graphs (where edges exist with 50% probability).
  • Scaling Analysis: They performed numerical calculations for gate counts on Erdös-Rényi graphs scaled up to 640 nodes to see how the overhead grows for larger, more realistic problems.

Key Insights and Ideas

  • Classical-for-Quantum Trade: The DQVA is a powerful "knob." By allowing for more iterations of classical optimization, you can significantly reduce the number of quantum gates required. This is a vital strategy for NISQ devices where quantum "coherence time" is the scarcest resource.
  • The Power of Native Toffolis: Supporting a native three-qubit gate (Toffoli) isn't just a minor upgrade; it consistently produces the shortest circuits across all graph sizes, often by orders of magnitude compared to standard CNOT-based decompositions.
  • Qutrits as "Free" Ancillae: Using qutrits ($S^3_2$) allows the system to use the third state ($|2\rangle$) as a temporary "scratchpad." This achieves the same efficiency as having many extra "ancilla" qubits without actually needing the extra physical hardware.
  • Fidelity Thresholds: The paper provides a "break-even" analysis for hardware designers. For example, a native Toffoli gate only needs to be about 97.8% accurate to be more beneficial than decomposing it into standard gates on a typical high-end NISQ system.

Key Results

  • Performance vs. Parameters: All three QAOA variants achieved high approximation ratios ($>0.95$) on 20-node graphs, but MA-QAOA and DQVA did so with much shorter quantum circuits than SA-QAOA.
  • Massive Gate Savings: For a 600-node graph, choosing the right decomposition and gate set can save as many as $1.6 \times 10^5$ entangling gates.
  • GDC Validation: The GDC metric successfully showed that lower-fidelity native gates (like a slightly noisier Toffoli) can still outperform higher-fidelity standard gates because the total number of operations required is so much lower.

Limitations and Future Work

  • Simulation-Based: The results are based on numerical simulations and theoretical gate counts. The next step is to validate these tradeoffs on actual quantum hardware (e.g., neutral atom or trapped ion systems that are beginning to support multi-qubit gates).
  • Noise Models: While GDC accounts for gate fidelity, it doesn't fully model complex noise effects like crosstalk or decoherence over time, which might affect the different QAOA variants differently.
  • Optimization Challenges: The DQVA requires more classical optimization rounds. As problem sizes grow, the "classical" part of the hybrid algorithm might become a bottleneck, a challenge known as "barren plateaus" in the optimization landscape.

Summary updated

Abstract

The computational capabilities of near-term quantum computers are limited by the noisy execution of gate operations and a limited number of physical qubits. Hybrid variational algorithms are well-suited to near-term quantum devices because they allow for a wide range of tradeoffs between the amount of quantum and classical resources used to solve a problem. This paper investigates tradeoffs available at both the algorithmic and hardware levels by studying a specific case -- applying the Quantum Approximate Optimization Algorithm (QAOA) to instances of the Maximum Independent Set (MIS) problem. We consider three variants of the QAOA which offer different tradeoffs at the algorithmic level in terms of their required number of classical parameters, quantum gates, and iterations of classical optimization needed. Since MIS is a constrained combinatorial optimization problem, the QAOA must respect the problem constraints. This can be accomplished by using many multi-controlled gate operations which must be decomposed into gates executable by the target hardware. We study the tradeoffs available at this hardware level, combining the gate fidelities and decomposition efficiencies of different native gate sets into a single metric called the gate decomposition cost.
BibTeX
@misc{tomesh2022quantum,
  author = {Teague Tomesh and Nicholas B. Allen and Zain H. Saleem and Saleem, Zain},
  title = {{Quantum-classical tradeoffs and multi-controlled quantum gate decompositions in variational algorithms}},
  year = {2022},
  eprint = {2210.04378},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2210.04378},
}
Figure