Quantum estimation bound of Gaussian matrix permanent

• URL: http://arxiv.org/abs/2205.01328v3
• Date: Tue, 23 Jul 2024 15:01:52 GMT
• Title: Quantum estimation bound of Gaussian matrix permanent
• Abstract summary: Exact calculation and even multiplicative error estimation of matrix permanent are challenging for both classical and quantum computers. Our newly developed formula for matrix permanents and its corresponding quantum expression have enabled better estimation of the average additive error.
• Score: 1.7404865362620803
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Exact calculation and even multiplicative error estimation of matrix permanent are challenging for both classical and quantum computers. Regarding the permanents of random Gaussian matrices, the additive error estimation is closely linked to boson sampling, and achieving multiplicative error estimation requires exponentially many samplings. Our newly developed formula for matrix permanents and its corresponding quantum expression have enabled better estimation of the average additive error for random Gaussian matrices compared to Gurvits' classical sampling algorithm. The well-known Ryser formula has been converted into a quantum permanent estimator. When dealing with real random Gaussian square matrices of size $N$, the quantum estimator can approximate the matrix permanent with an additive error smaller than $\epsilon(\sqrt{\mathrm{e}N})^{N}$, where $\epsilon$ is the estimation precision. In contrast, Gurvits' classical sampling algorithm has an estimation error of $\epsilon(2\sqrt{N})^{N}$, which is exponentially larger ($1.2^{N}$) than the quantum method. As expected, the quantum additive error bound fails to reach the multiplicative error bound of $(2\pi N)^{1/4}\epsilon(\sqrt{N/\mathrm{e}})^{N}$. Additionally, the quantum permanent estimator can be up to quadratically faster than the classical estimator when using quantum phase estimation-based amplitude estimation.

Related papers

• Improved Measurement Cost Scaling in the Nonorthogonal Quantum Eigensolver [1.6328866317851187]
  We study a bottleneck for the nonorthogonal quantum eigensolver (NOQE)<n>We show that, after overlap thresholding, the eigenvalue sensitivity is controlled by the condition number of the retained overlap matrix.<n>Experiments on hydrogen chains and rings suggest that, in practice, the measurement cost of structured NOQE instances can grow even more slowly than this linear bound.
  arXiv  Detail & Related papers  (2026-08-13T05:05:55Z)
• Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise [49.730496294398726]
  We develop a novel quantum mean estimator for heavy-tailed random variables.<n>We derive stronger lower bounds for tail index>4/3$, showing that a nontrivial dependence on a dimension is unavoidable.<n>For a convex objective function, we propose a quantum projected gradient descent method.
  arXiv  Detail & Related papers  (2026-07-28T09:29:37Z)
• Quantum Sampling and Moment Estimation for Transformed Gaussian Random Fields [0.0]
  We present a quantum algorithm for efficiently sampling transformed Gaussian random fields on $d$-dimensional domains.<n>Pointwise transformations enforcing boundedness are essential for using Gaussian random fields in quantum computation.
  arXiv  Detail & Related papers  (2025-08-19T14:42:52Z)
• Quantum computation with the eigenstate thermalization hypothesis instead of wavefunction preparation [0.0]
  The eigenstate thermalization hypothesis connects a time-average of expectation values for non-integrable systems to the normalized trace of an operator. It is shown here that the hypothesis can be a suitable way to take an expectation value over an equal superposition of eigenstates on the quantum computer.
  arXiv  Detail & Related papers  (2025-04-27T10:20:07Z)
• Matrix encoding method in variational quantum singular value decomposition [49.494595696663524]
  Conditional measurement is involved to avoid small success probability in ancilla measurement. The objective function for the algorithm can be obtained probabilistically via measurement of the state of a one-qubit subsystem.
  arXiv  Detail & Related papers  (2025-03-19T07:01:38Z)
• Heisenberg-limited adaptive gradient estimation for multiple observables [0.39102514525861415]
  In quantum mechanics, measuring the expectation value of a general observable has an inherent statistical uncertainty. We provide an adaptive quantum algorithm for estimating the expectation values of $M$ general observables within root mean squared error. Our method paves a new way to precisely understand and predict various physical properties in complicated quantum systems using quantum computers.
  arXiv  Detail & Related papers  (2024-06-05T14:16:47Z)
• Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
  We study the problem of estimating frequency response functions of systems of coupled, classical harmonic oscillators using a quantum computer. Our proposed quantum algorithm operates in the standard $s-sparse, oracle-based query access model. We show that a simple adaptation of our algorithm solves the random glued-trees problem in time.
  arXiv  Detail & Related papers  (2024-05-14T15:28:37Z)
• Vectorization of the density matrix and quantum simulation of the von Neumann equation of time-dependent Hamiltonians [65.268245109828]
  We develop a general framework to linearize the von-Neumann equation rendering it in a suitable form for quantum simulations. We show that one of these linearizations of the von-Neumann equation corresponds to the standard case in which the state vector becomes the column stacked elements of the density matrix. A quantum algorithm to simulate the dynamics of the density matrix is proposed.
  arXiv  Detail & Related papers  (2023-06-14T23:08:51Z)
• 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)
• Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants [8.453228628258778]
  We develop quantum algorithms for sampling logconcave distributions and for estimating their normalizing constants. We exploit quantum analogs of the Monte Carlo method and quantum walks. We also prove a $1/epsilon1-o(1)$ quantum lower bound for estimating normalizing constants.
  arXiv  Detail & Related papers  (2022-10-12T19:10:43Z)
• Trimmed Sampling Algorithm for the Noisy Generalized Eigenvalue Problem [0.0]
  Solving the generalized eigenvalue problem is a useful method for finding energy eigenstates of large quantum systems. The problem is especially bad when matrix elements are evaluated using methods and have significant error bars. We introduce the trimmed sampling algorithm in order to solve this problem.
  arXiv  Detail & Related papers  (2022-09-05T18:10:12Z)
• 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)
• Quantum algorithms for spectral sums [50.045011844765185]
  We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices. We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory.
  arXiv  Detail & Related papers  (2020-11-12T16:29:45Z)
• The limits of quantum circuit simulation with low precision arithmetic [0.0]
  The goal is to estimate how much memory can be saved in simulations that involve random, maximally entangled quantum states. An arithmetic polar representation of $B$ bits is defined for each quantum amplitude. A model is developed to quantify the cumulative errors on a circuit of $Q$ qubits and $G$ gates.
  arXiv  Detail & Related papers  (2020-05-27T14:48:31Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)

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.