Optimal quantum circuit cuts with application to clustered Hamiltonian simulation

Abstract

We study methods to replace entangling operations with random local operations in a quantum computation, at the cost of increasing the number of required executions. First, we consider "space-like cuts" where an entangling unitary is replaced with random local unitaries. We propose an entanglement measure for quantum dynamics, the product extent, which bounds the cost in a procedure for this replacement based on two copies of the Hadamard test. In the terminology of prior work, this procedure yields a quasiprobability decomposition with minimal 1-norm in a number of cases, which addresses an open question of Piveteau and Sutter. As an application, we give an improved algorithm for clustered Hamiltonian simulation. Specifically we show that interactions can be removed at a cost which is exponential in the sum of their strengths times the evolution time, and vanishing in the limit of weak interactions. We also give an improved upper bound on the cost of replacing wires with measure-and-prepare channels using "time-like cuts''. We prove a matching information-theoretic lower bound when estimating output probabilities.

35 pages, 3 figures; v2: updated Fig. 1, additional comparison to prior work in Sec. 1, details added to some proofs

References in corpus (22)

• The logarithmic negativity: A full entanglement monotone that is not convex
• Predicting Many Properties of a Quantum System from Very Few Measurements
• General Entanglement Breaking Channels
• A Theory of Trotter Error
• Quantum Data Hiding
• Quantum Algorithms for Fermionic Simulations
• Trading classical and quantum computational resources
• Simulation of quantum circuits by low-rank stabilizer decompositions
• Simulating Large Quantum Circuits on a Small Quantum Computer
• Quantum dynamics as a physical resource
• Doubling the size of quantum simulators by entanglement forging
• Distinguishability of quantum states under restricted families of measurements with an application to quantum data hiding
• How robust is a quantum gate in the presence of noise?
• Circuit knitting with classical communication
• Constructing a virtual two-qubit gate by sampling single-qubit operations
• Quantum simulation with hybrid tensor networks
• Fast quantum circuit cutting with randomized measurements
• Overhead for simulating a non-local channel with local channels by quasiprobability sampling
• Universal and Operational Benchmarking of Quantum Memories
• Generating a state $t$-design by diagonal quantum circuits
• Relations for certain symmetric norms and anti-norms before and after partial trace
• Perturbative quantum simulation

Cited by in corpus (6)

• Networked Quantum Services
• Fault-tolerant quantum algorithms for quantum molecular systems: A survey
• Cutting circuits with multiple two-qubit unitaries
• TE-PAI: Exact Time Evolution by Sampling Random Circuits
• Resource-efficient Generalized Quantum Subspace Expansion
• Circuit cutting with classical side information