Complexity of quantum state verification in the quantum linear systems problem

• URL: http://arxiv.org/abs/2007.15698v2
• Date: Tue, 23 Feb 2021 18:25:28 GMT
• Title: Complexity of quantum state verification in the quantum linear systems problem
• Authors: Rolando D. Somma and Yigit Subasi
• Abstract summary: We analyze the complexity of quantum state verification in the context of solving systems of linear equations of the form $A vec x = vec b$. We show that any quantum operation that verifies whether a given quantum state is within a constant distance from the solution of the quantum linear systems problem requires $q=Omega(kappa)$.
• Score: 0.12891210250935145
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We analyze the complexity of quantum state verification in the context of solving systems of linear equations of the form $A \vec x = \vec b$. We show that any quantum operation that verifies whether a given quantum state is within a constant distance from the solution of the quantum linear systems problem requires $q=\Omega(\kappa)$ uses of a unitary that prepares a quantum state $\left| b \right>$, proportional to $\vec b$, and its inverse in the worst case. Here, $\kappa$ is the condition number of the matrix $A$. For typical instances, we show that $q=\Omega(\sqrt \kappa)$ with high probability. These lower bounds are almost achieved if quantum state verification is performed using known quantum algorithms for the quantum linear systems problem. We also analyze the number of copies of $\left| b \right>$ required by verification procedures of the prepare and measure type. In this case, the lower bounds are quadratically worse, being $\Omega(\kappa^2)$ in the worst case and $\Omega(\kappa)$ in typical instances with high probability. We discuss the implications of our results to known variational and related approaches to this problem, where state preparation, gate, and measurement errors will need to decrease rapidly with $\kappa$ for worst-case and typical instances if error correction is not used, and present some open problems.

Related papers

• Tight Quantum Depth Lower Bound for Solving Systems of Linear Equations [7.319050391449301]
  We show that any quantum algorithm for solving systems of linear equations with time complexity has a lower bound on $Omega(kappa)$ on the depth of queries. The state-of-the-art quantum algorithm for this problem is due to Costa, An, Sanders, Su, Babbush, and Berry (2022), with optimal query complexity $Theta(kappa)$.
  arXiv  Detail & Related papers  (2024-07-08T15:05:46Z)
• 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)
• A generalized framework for quantum state discrimination, hybrid algorithms, and the quantum change point problem [3.4683494246563606]
  We present a hybrid quantum-classical algorithm based on semidefinite programming to calculate the maximum reward when the states are pure and have efficient circuits. We give now-possible algorithms for the quantum change point identification problem which asks, given a sequence of quantum states, determine the time steps when the quantum states changed.
  arXiv  Detail & Related papers  (2023-12-07T03:42:40Z)
• 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)
• 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 Algorithm for Fidelity Estimation [8.270684567157987]
  For two unknown mixed quantum states $rho$ and $sigma$ in an $N$-dimensional space, computing their fidelity $F(rho,sigma)$ is a basic problem. We propose a quantum algorithm that solves this problem in $namepoly(log (N), r, 1/varepsilon)$ time.
  arXiv  Detail & Related papers  (2021-03-16T13:57:01Z)
• Efficient Verification of Anticoncentrated Quantum States [0.38073142980733]
  I present a novel method for estimating the fidelity $F(mu,tau)$ between a preparable quantum state $mu$ and a classically specified target state $tau$. I also present a more sophisticated version of the method, which uses any efficiently preparable and well-characterized quantum state as an importance sampler.
  arXiv  Detail & Related papers  (2020-12-15T18:01:11Z)
• 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)
• Bosonic quantum communication across arbitrarily high loss channels [68.58838842613457]
  A general attenuator $Phi_lambda, sigma$ is a bosonic quantum channel that acts by combining the input with a fixed environment state. We show that for any arbitrary value of $lambda>0$ there exists a suitable single-mode state $sigma(lambda)$. Our result holds even when we fix an energy constraint at the input of the channel, and implies that quantum communication at a constant rate is possible even in the limit of arbitrarily low transmissivity.
  arXiv  Detail & Related papers  (2020-03-19T16:50:11Z)
• Quantum Coupon Collector [62.58209964224025]
  We study how efficiently a $k$-element set $Ssubseteq[n]$ can be learned from a uniform superposition $|Srangle of its elements. We give tight bounds on the number of quantum samples needed for every $k$ and $n$, and we give efficient quantum learning algorithms.
  arXiv  Detail & Related papers  (2020-02-18T16:14:55Z)
• Variational Quantum Linear Solver [0.3774866290142281]
  We propose a hybrid quantum-classical algorithm for solving linear systems on near-term quantum computers. We numerically solve non-trivial problems of size up to $250times250$ using Rigetti's quantum computer.
  arXiv  Detail & Related papers  (2019-09-12T17:28:09Z)

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.