Resource-Optimal Importance Sampling for Randomized Quantum Algorithms

• URL: http://arxiv.org/abs/2603.13495v1
• Date: Fri, 13 Mar 2026 18:17:33 GMT
• Title: Resource-Optimal Importance Sampling for Randomized Quantum Algorithms
• Abstract summary: We introduce a general framework for applying classical importance sampling to randomized quantum protocols.<n>Given a cost function for running quantum circuits, the proposed approach minimizes a net-cost figure of merit.<n>We extend the framework to scenarios where the quantum computation is subject to errors arising from algorithmic approximations or from physical noise.
• Score: 3.797867929356259
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Randomized protocols are procedures that incorporate probabilistic choices during their execution and they play a central role in quantum algorithms, spanning Hamiltonian simulation, noise mitigation, and measurement tasks. In practical implementations, the dominant cost of such protocols typically arises from circuit execution and measurement, and depends on hardware-specific resources such as gate counts, circuit depth, runtime, or dissipated energy. We introduce a general framework for applying classical importance sampling to randomized quantum protocols. Given a cost function for running quantum circuits, the proposed approach minimizes a net-cost figure of merit that jointly captures the computational expense per circuit and the estimator variance. We further extend the framework to scenarios where the quantum computation is subject to errors arising either from algorithmic approximations or from physical noise, proving that importance sampling preserves estimator bias despite altering the sampling distribution, and to settings with error-detection schemes, where we characterize the resulting changes in the optimal sampling strategy and achievable net-cost reduction. Representative applications include the Qdrift protocol, dephasing channels, mixed-states simulation, composite observables estimation, classical shadows, and probabilistic error cancellation. Overall, our results establish a principled approach for reducing the computational resources required by randomized quantum protocols through classical sampling optimization.

Related papers

• Efficient re-sampling in quasi-probability decompositions [0.4666493857924357]
  Near-term quantum devices are limited by noise and hardware constraints, motivating algorithmic approaches that trade circuit complexity for increased sampling overhead.<n>We introduce a reweighting strategy for QPDs for circuits with the same variational structure across parameter settings, reusing samples and thereby reducing the sampling overhead.
  arXiv  Detail & Related papers  (2026-08-03T11:24:32Z)
• Stochastic Pauli-path simulator for large-scale quantum optimization [57.179828941706006]
  Pauli-path simulators offer a promising route to large-scale classical simulation of quantum circuits in the low-magic regime.<n>Existing approaches either lack native support for gradient-based optimization or suffer from severe gradient bias.<n>Here we propose the Pauli-path simulator (SPPS), a computational framework for large-scale quantum optimization.
  arXiv  Detail & Related papers  (2026-07-20T10:43:44Z)
• Classical algorithms for measurement-adaptive Gaussian circuits [0.1909808926064466]
  We study the quantum mean-value problem, estimating observable expectation values that underpin simulation and variational algorithms.<n>We analyze bosonic circuits with adaptivity and prove that when the number of adaptive measurements is small, the mean-value problem admits efficient classical algorithms.
  arXiv  Detail & Related papers  (2025-08-31T08:39:58Z)
• Universal Quantum Error Mitigation via Random Inverse Depolarizing Approximation [45.88028371034407]
  We introduce RIDA (Random Inverse Depolarizing Approximation), a simple universal method that harnesses randomly generated circuits to estimate a given circuit's global depolarization probability and corresponding error-free expectation value.<n> Numerical tests indicate RIDA outperforms key benchmarks, suggestive of significant accuracy improvements for applications of quantum computing across fields including physics and chemistry.
  arXiv  Detail & Related papers  (2025-08-24T20:30:08Z)
• Quantum Internet: Resource Estimation for Entanglement Routing [0.0]
  We investigate the dependence of resource scaling of networks on realistic experimental errors.<n>Our error model predicts substantially stricter thresholds for efficient network operation than previously suggested.<n>We find that trapped ions and color centers in diamond currently provide the best route towards large-scale networks.
  arXiv  Detail & Related papers  (2024-10-14T13:50:39Z)
• Measurement-Based Quantum Approximate Optimization [0.24861619769660645]
  We focus on measurement-based quantum computing protocols for approximate optimization. We derive measurement patterns for applying QAOA to the broad and important class of QUBO problems. We discuss the resource requirements and tradeoffs of our approach to that of more traditional quantum circuits.
  arXiv  Detail & Related papers  (2024-03-18T06:59:23Z)
• Dynamical subset sampling of quantum error correcting protocols [0.0]
  We show the capabilities of dynamical subset sampling with examples from fault-tolerant (FT) QEC. We show that, in a typical stabilizer simulation with incoherent Pauli noise of strength $p = 10-3$, our method can reach a required sampling accuracy on the logical failure rate.
  arXiv  Detail & Related papers  (2023-09-22T10:32:20Z)
• Randomized semi-quantum matrix processing [0.0]
  We present a hybrid quantum-classical framework for simulating generic matrix functions. The method is based on randomization over the Chebyshev approximation of the target function. We prove advantages on average depths, including quadratic speed-ups on costly parameters.
  arXiv  Detail & Related papers  (2023-07-21T18:00:28Z)
• Importance sampling for stochastic quantum simulations [68.8204255655161]
  We introduce the qDrift protocol, which builds random product formulas by sampling from the Hamiltonian according to the coefficients. We show that the simulation cost can be reduced while achieving the same accuracy, by considering the individual simulation cost during the sampling stage. Results are confirmed by numerical simulations performed on a lattice nuclear effective field theory.
  arXiv  Detail & Related papers  (2022-12-12T15:06:32Z)
• End-to-end resource analysis for quantum interior point methods and portfolio optimization [63.4863637315163]
  We provide a complete quantum circuit-level description of the algorithm from problem input to problem output. We report the number of logical qubits and the quantity/depth of non-Clifford T-gates needed to run the algorithm.
  arXiv  Detail & Related papers  (2022-11-22T18:54:48Z)
• Decomposition of Matrix Product States into Shallow Quantum Circuits [62.5210028594015]
  tensor network (TN) algorithms can be mapped to parametrized quantum circuits (PQCs) We propose a new protocol for approximating TN states using realistic quantum circuits. Our results reveal one particular protocol, involving sequential growth and optimization of the quantum circuit, to outperform all other methods.
  arXiv  Detail & Related papers  (2022-09-01T17:08:41Z)
• Learnability of the output distributions of local quantum circuits [53.17490581210575]
  We investigate, within two different oracle models, the learnability of quantum circuit Born machines. We first show a negative result, that the output distributions of super-logarithmic depth Clifford circuits are not sample-efficiently learnable. We show that in a more powerful oracle model, namely when directly given access to samples, the output distributions of local Clifford circuits are computationally efficiently PAC learnable.
  arXiv  Detail & Related papers  (2021-10-11T18:00:20Z)
• Error mitigation and quantum-assisted simulation in the error corrected regime [77.34726150561087]
  A standard approach to quantum computing is based on the idea of promoting a classically simulable and fault-tolerant set of operations. We show how the addition of noisy magic resources allows one to boost classical quasiprobability simulations of a quantum circuit.
  arXiv  Detail & Related papers  (2021-03-12T20:58:41Z)

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.