Optimal quantum circuit cuts with application to clustered Hamiltonian simulation

• URL: http://arxiv.org/abs/2403.01018v2
• Date: Tue, 17 Dec 2024 20:58:10 GMT
• Title: Optimal quantum circuit cuts with application to clustered Hamiltonian simulation
• Abstract summary: 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.<n>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.<n>As an application, 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.
• Score: 0.8287206589886879
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Half the Interference, Most of the Answer: Approximate Quantum Simulation via Path-Sum Pruning [0.15554111333620432]
  We introduce statistical interference sampling, a framework that makes this second bottleneck explicit.<n>On benchmark circuits for Deutsch-Jozsa, Grover search, Simon's problem, and small Shor period-finding instances, we find that nearly 50% of endpoint interference reactions can be omitted.
  arXiv  Detail & Related papers  (2026-06-01T08:57:44Z)
• Constant-Factor Improvements in Quantum Algorithms for Linear Differential Equations [0.46664938579243576]
  We prove constant factor bounds for a promising new quantum differential equation solver, the linear combination of Hamiltonian simulation algorithm.<n>Our new formulae improve over previous state of the art by at least two orders of magnitude, where the speedup can be far greater if state preparation has a significant cost.
  arXiv  Detail & Related papers  (2025-06-25T18:50:44Z)
• Joint Cutting for Hybrid Schrödinger-Feynman Simulation of Quantum Circuits [4.1053323247531255]
  "Joint cutting" can outperform the standard HSF simulation by up to a factor $approx 4000times$. The proposed refinement can help decrease simulation times and highlight the remaining challenges.
  arXiv  Detail & Related papers  (2025-02-10T19:01:04Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Fast quantum circuit cutting with randomized measurements [0.0]
  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.
  arXiv  Detail & Related papers  (2022-07-29T15:13:04Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• Commutation simulator for open quantum dynamics [0.0]
  We propose an innovative method to investigate directly the properties of a time-dependent density operator $hatrho(t)$. We can directly compute the expectation value of the commutation relation and thus of the rate of change of $hatrho(t)$. A simple but important example is demonstrated in the single-qubit case and we discuss extension of the method for practical quantum simulation with many qubits.
  arXiv  Detail & Related papers  (2022-06-01T16:03:43Z)
• Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
  We present a framework for constructing mixing operators that restrict the evolution to a subspace of the full Hilbert space. We generalize the "XY"-mixer designed to preserve the subspace of "one-hot" states to the general case of subspaces given by a number of computational basis states. Our analysis also leads to valid Trotterizations for "XY"-mixer with fewer CX gates than is known to date.
  arXiv  Detail & Related papers  (2022-03-11T17:19:26Z)
• A hierarchy of efficient bounds on quantum capacities exploiting symmetry [8.717253904965371]
  We exploit the recently introduced $D#$ in order to obtain a hierarchy of semidefinite programming bounds on various regularized quantities. As applications, we give a general procedure to give efficient bounds on the regularized Umegaki channel divergence. We prove that for fixed input and output dimensions, the regularized sandwiched R'enyi divergence between any two quantum channels can be approximated up to an $epsilon$ accuracy in time.
  arXiv  Detail & Related papers  (2022-03-04T04:34:15Z)
• Nystr\"om Kernel Mean Embeddings [92.10208929236826]
  We propose an efficient approximation procedure based on the Nystr"om method. It yields sufficient conditions on the subsample size to obtain the standard $n-1/2$ rate. We discuss applications of this result for the approximation of the maximum mean discrepancy and quadrature rules.
  arXiv  Detail & Related papers  (2022-01-31T08:26:06Z)
• Average-case Speedup for Product Formulas [69.68937033275746]
  Product formulas, or Trotterization, are the oldest and still remain an appealing method to simulate quantum systems. We prove that the Trotter error exhibits a qualitatively better scaling for the vast majority of input states. Our results open doors to the study of quantum algorithms in the average case.
  arXiv  Detail & Related papers  (2021-11-09T18:49:48Z)
• Halving the cost of quantum multiplexed rotations [0.0]
  We improve the number of $T$ gates needed for a $b$-bit approximation of a multiplexed quantum gate with $c$ controls. Our results roughly halve the cost of state-of-art electronic structure simulations based on qubitization of double-factorized or tensor-hypercontracted representations.
  arXiv  Detail & Related papers  (2021-10-26T06:49:44Z)
• Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs [45.87981728307819]
  The ability to compare and align related datasets living in heterogeneous spaces plays an increasingly important role in machine learning. The Gromov-Wasserstein (GW) formalism can help tackle this problem.
  arXiv  Detail & Related papers  (2021-06-02T12:50:56Z)
• Implementation of Measurement Reduction for the Variational Quantum Eigensolver [0.0]
  Unitary partitioning reduces overhead by transforming the problem Hamiltonian into one containing fewer terms. To our knowledge, this work also demonstrates the first experimental implementation of LCU on quantum hardware.
  arXiv  Detail & Related papers  (2020-12-04T18:29:26Z)
• Random quantum circuits anti-concentrate in log depth [118.18170052022323]
  We study the number of gates needed for the distribution over measurement outcomes for typical circuit instances to be anti-concentrated. Our definition of anti-concentration is that the expected collision probability is only a constant factor larger than if the distribution were uniform. In both the case where the gates are nearest-neighbor on a 1D ring and the case where gates are long-range, we show $O(n log(n)) gates are also sufficient.
  arXiv  Detail & Related papers  (2020-11-24T18:44:57Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.