Fast quantum circuit cutting with randomized measurements

Abstract

We propose a new method to extend the size of a quantum computation beyond the number of physical qubits available on a single device. This is accomplished by randomly inserting measure-and-prepare channels to express the output state of a large circuit as a separable state across distinct devices. Our method employs randomized measurements, resulting in a sample overhead that is $\tilde{O}(4^k/{\epsilon }^2)$, where $\epsilon$ is the accuracy of the computation and $k$ the number of parallel wires that are "cut" to obtain smaller sub-circuits. We also show an information-theoretic lower bound of $\Omega (2^k/{\epsilon }^2)$ for any comparable procedure. We use our techniques to show that circuits in the Quantum Approximate Optimization Algorithm (QAOA) with $p$ entangling layers can be simulated by circuits on a fraction of the original number of qubits with an overhead that is roughly $2^{O(p\kappa )}$, where $\kappa$ is the size of a known balanced vertex separator of the graph which encodes the optimization problem. We obtain numerical evidence of practical speedups using our method applied to the QAOA, compared to prior work. Finally, we investigate the practical feasibility of applying the circuit cutting procedure to large-scale QAOA problems on clustered graphs by using a $30$-qubit simulator to evaluate the variational energy of a $129$-qubit problem as well as carry out a $62$-qubit optimization.

9 pages, 6 figures

References in corpus (7)

• A Quantum Approximate Optimization Algorithm
• A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples
• Quantum Divide and Compute: Hardware Demonstrations and Noisy Simulations
• ScaleQC: A Scalable Framework for Hybrid Computation on Quantum and Classical Processors
• Large-scale Quantum Approximate Optimization via Divide-and-Conquer

Cited by in corpus (28)

• Review of Distributed Quantum Computing. From single QPU to High Performance Quantum Computing
• State Preparation on Quantum Computers via Quantum Steering
• Investigating the effect of circuit cutting in QAOA for the MaxCut problem on NISQ devices
• Cutting multi-control quantum gates with ZX calculus
• A performance characterization of quantum generative models
• Resource Saving via Ensemble Techniques for Quantum Neural Networks
• Doubly optimal parallel wire cutting without ancilla qubits
• Networked Quantum Services
• Optimal joint cutting of two-qubit rotation gates
• Quantum circuit compilation and hybrid computation using Pauli-based computation
• Optimal quantum circuit cuts with application to clustered Hamiltonian simulation
• Cutting circuits with multiple two-qubit unitaries
• Distributed Quantum Computing for Chemical Applications
• Accuracy vs Memory Advantage in the Quantum Simulation of Stochastic Processes
• Optimal wire cutting with classical communication
• Random Natural Gradient
• Joint Wire Cutting with Non-Maximally Entangled States
• Quantum channel decomposition with pre- and post-selection
• Perspectives on Utilization of Measurements in Quantum Algorithms
• Parallel Quantum Signal Processing Via Polynomial Factorization
• Distributing Quantum Computations, Shot-wise
• Parallelized Givens Ansatz for Molecular ground-states: Bridging Accuracy and Efficiency on NISQ Platforms
• Three ways to share a QPU: Scheduling strategies for hybrid Quantum-HPC applications
• Implementation of Tensor Network Simulation TN-Sim under NWQ-Sim
• Circuit Folding: Scalable and Graph-Based Circuit Cutting via Modular Structure Exploitation
• Quantum simulation in the entanglement picture
• Joint Cutting for Hybrid Schrödinger-Feynman Simulation of Quantum Circuits
• Hybrid Classical-Quantum Simulation of MaxCut using QAOA-in-QAOA