Quantum-classical tradeoffs and multi-controlled quantum gate decompositions in variational algorithms
arXiv:2210.04378 · doi:10.22331/q-2024-10-04-1493
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.
21 pages, 11 figures, 5 tables
References in corpus (37)
- Quantum Computing in the NISQ era and beyond
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- Elementary gates for quantum computation
- Variational Quantum Algorithms
- A Quantum Approximate Optimization Algorithm
- Suppressing quantum errors by scaling a surface code logical qubit
- From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
- Quantum computing with atomic qubits and Rydberg interactions: Progress and challenges
- Building logical qubits in a superconducting quantum computing system
- Quantum circuits with many photons on a programmable nanophotonic chip
- Benchmarking an 11-qubit quantum computer
- Realization of the quantum Toffoli gate with trapped ions
- Warm-starting quantum optimization
- Efficient decomposition of quantum gates
- Quantum Circuits for Isometries
- Qutrit randomized benchmarking
- Optimized Compilation of Aggregated Instructions for Realistic Quantum Computers
- Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem
- High-fidelity three-qubit iToffoli gate for fixed-frequency superconducting qubits
- Fast multi-qubit gates by adiabatic evolution in interacting excited state manifolds
- Asymptotic Improvements to Quantum Circuits via Qutrits
- Parameter Transfer for Quantum Approximate Optimization of Weighted MaxCut
- Compiling quantum algorithms for architectures with multi-qubit gates
- Single-step implementation of high fidelity -bit Toffoli gate
- Universal quantum circuits for quantum chemistry
- Efficient Grover search with Rydberg blockade
- -body interactions between trapped ion qubits via spin-dependent squeezing
- Improved error thresholds for measurement-free error correction
- Approaching the theoretical limit in quantum gate decomposition
- The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model
- Elementary gates for ternary quantum logic circuit
- Designing calibration and expressivity-efficient instruction sets for quantum computing
- Approaches to Constrained Quantum Approximate Optimization
- Fault-tolerant measurement-free quantum error correction with multi-qubit gates
- Quantum Local Search with the Quantum Alternating Operator Ansatz
- Grover search algorithm with Rydberg-blockaded atoms: Quantum Monte Carlo simulations
- A high-fidelity method for a single-step -bit Toffoli gate in trapped ions