Doubly optimal parallel wire cutting without ancilla qubits

Abstract

A restriction in the quality and quantity of available qubits presents a substantial obstacle to the application of near-term and early fault-tolerant quantum computers in practical tasks. To confront this challenge, some techniques for effectively augmenting the system size through classical processing have been proposed; one promising approach is quantum circuit cutting. The main idea of quantum circuit cutting is to decompose an original circuit into smaller sub-circuits and combine outputs from these sub-circuits to recover the original output. Although this approach enables us to simulate larger quantum circuits beyond physically available circuits, it needs classical overheads quantified by the two metrics: the sampling overhead in the number of measurements to reconstruct the original output, and the number of channels in the decomposition. Thus, it is crucial to devise a decomposition method that minimizes both of these metrics, thereby reducing the overall execution time. This paper studies the problem of decomposing the parallel $n$-qubit identity channel, i.e., $n$-parallel wire cutting, into a set of local operations and classical communication; then we give an optimal wire-cutting method comprised of channels based on mutually unbiased bases, that achieves minimal overheads in both the sampling overhead and the number of channels, without ancilla qubits. This is in stark contrast to the existing method that achieves the optimal sampling overhead yet with ancilla qubits. Moreover, we derive a tight lower bound of the number of channels in parallel wire cutting without ancilla systems and show that only our method achieves this lower bound among the existing methods. Notably, our method shows an exponential improvement in the number of channels, compared to the aforementioned ancilla-assisted method that achieves optimal sampling overhead.

arXiv commentSubstantially updated version. 33 pages, 10 figures

References in corpus (50)

• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• A variational eigenvalue solver on a quantum processor
• Hardware-efficient Variational Quantum Eigensolver for Small Molecules and Quantum Magnets
• Supervised learning with quantum enhanced feature spaces
• Improved Simulation of Stabilizer Circuits
• Error mitigation for short-depth quantum circuits
• Predicting Many Properties of a Quantum System from Very Few Measurements
• Quantum Error Correction and Orthogonal Geometry
• Exact and Approximate Unitary 2-Designs: Constructions and Applications
• Distributed Quantum Computation over Noisy Channels
• Quantum optimization using variational algorithms on near-term quantum devices
• Quantum Error Mitigation
• General Entanglement Breaking Channels
• Robustness of entanglement
• A new proof for the existence of mutually unbiased bases
• Practical Quantum Error Mitigation for Near-Future Applications
• Theory of variational quantum simulation
• Substituting Quantum Entanglement for Communication
• Application of a resource theory for magic states to fault-tolerant quantum computing
• Evenly distributed unitaries: on the structure of unitary designs
• Trading classical and quantum computational resources
• Simulating Large Quantum Circuits on a Small Quantum Computer
• Estimating outcome probabilities of quantum circuits using quasiprobabilities
• Gate Set Tomography
• Efficient quantum measurement of Pauli operators in the presence of finite sampling error
• Simulating positive-operator-valued measures with projective measurements
• Doubling the size of quantum simulators by entanglement forging
• Hardware-efficient variational quantum algorithms for time evolution
• Mutually unbiased binary observable sets on N qubits
• CutQC: Using Small Quantum Computers for Large Quantum Circuit Evaluations
• Quantifying quantum speedups: improved classical simulation from tighter magic monotones
• Quantifying magic for multi-qubit operations
• Unitary designs and codes
• Circuit knitting with classical communication
• A quantum-classical cloud platform optimized for variational hybrid algorithms
• A resource theory of quantum memories and their faithful verification with minimal assumptions
• Constructing a virtual two-qubit gate by sampling single-qubit operations
• A case study of variational quantum algorithms for a job shop scheduling problem
• Quantum simulation with hybrid tensor networks
• Fast quantum circuit cutting with randomized measurements
• Quasiprobability decompositions with reduced sampling overhead
• On Approximately Symmetric Informationally Complete Positive Operator-Valued Measures and Related Systems of Quantum States
• Overhead for simulating a non-local channel with local channels by quasiprobability sampling
• Universal and Operational Benchmarking of Quantum Memories
• Experimental Simulation of Larger Quantum Circuits with Fewer Superconducting Qubits
• Cutting multi-control quantum gates with ZX calculus
• Simulating Time Evolution with Fully Optimized Single-Qubit Gates on Parameterized Quantum Circuits
• Fast Partitioning of Pauli Strings into Commuting Families for Optimal Expectation Value Measurements of Dense Operators
• Fast Classical Simulation of Hamiltonian Dynamics by Simultaneous Diagonalization Using Clifford Transformation with Parallel Computation
• Quantum channel decomposition with pre- and post-selection

Cited by in corpus (12)

• Review of Distributed Quantum Computing. From single QPU to High Performance Quantum Computing
• Quantum computing quantum Monte Carlo with hybrid tensor network for electronic structure calculations
• Cutting circuits with multiple two-qubit unitaries
• QuTracer: Mitigating Quantum Gate and Measurement Errors by Tracing Subsets of Qubits
• Joint Wire Cutting with Non-Maximally Entangled States
• Resource-efficient Generalized Quantum Subspace Expansion
• A Cross-Platform Execution Engine for the Quantum Intermediate Representation
• Density matrix representation of hybrid tensor networks for noisy quantum devices
• Circuit Folding: Scalable and Graph-Based Circuit Cutting via Modular Structure Exploitation
• Joint Cutting for Hybrid Schrödinger-Feynman Simulation of Quantum Circuits
• Improving the trainability of VQE on NISQ computers for solving portfolio optimization using convex interpolation
• Unitary-transformed projective squeezing: applications for circuit-knitting and state-preparation of non-Gaussian states