Quantum Event Learning and Gentle Random Measurements

• URL: http://arxiv.org/abs/2210.09155v4
• Date: Fri, 8 Mar 2024 19:40:15 GMT
• Title: Quantum Event Learning and Gentle Random Measurements
• Authors: Adam Bene Watts and John Bostanci
• Abstract summary: We prove the expected disturbance caused to a quantum system by a sequence of randomly ordered projective measurements is upper bounded by the square root of the probability that at least one measurement accepts. We also consider problems in which we are given sample access to an unknown state $rho$ and asked to estimate properties of the accepting probabilities.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We prove the expected disturbance caused to a quantum system by a sequence of randomly ordered two-outcome projective measurements is upper bounded by the square root of the probability that at least one measurement in the sequence accepts. We call this bound the Gentle Random Measurement Lemma. We then consider problems in which we are given sample access to an unknown state $\rho$ and asked to estimate properties of the accepting probabilities $\text{Tr}[M_i \rho]$ of a set of measurements $\{M_1, M_2, \ldots , M_m\}$. We call these types of problems Quantum Event Learning Problems. Using the gentle random measurement lemma, we show randomly ordering projective measurements solves the Quantum OR problem, answering an open question of Aaronson. We also give a Quantum OR protocol which works on non-projective measurements but which requires a more complicated type of measurement, which we call a Blended Measurement. Given additional guarantees on the set of measurements $\{M_1, \ldots, M_m\}$, we show the Quantum OR protocols developed in this paper can also be used to find a measurement $M_i$ such that $\text{Tr}[M_i \rho]$ is large. We also give a blended measurement based protocol for estimating the average accepting probability of a set of measurements on an unknown state. Finally we consider the Threshold Search Problem described by O'Donnell and B\u{a}descu. By building on our Quantum Event Finding result we show that randomly ordered (or blended) measurements can be used to solve this problem using $O(\log^2(m) / \epsilon^2)$ copies of $\rho$. Consequently, we obtain an algorithm for Shadow Tomography which requires $\tilde{O}(\log^2(m)\log(d)/\epsilon^4)$ samples, matching the current best known sample complexity. This algorithm does not require injected noise in the quantum measurements, but does require measurements to be made in a random order and so is no longer online.

Related papers

• Quantum state testing with restricted measurements [30.641152457827527]
  We develop an information-theoretic framework that yields unified copy complexity lower bounds for restricted families of non-adaptive measurements. We demonstrate a separation between these two schemes, showing the power of randomized measurement schemes over fixed ones.
  arXiv  Detail & Related papers  (2024-08-30T17:48:00Z)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  We show that any efficient SQ algorithm for the problem requires sample complexity at least $Omega(d1/2/(maxp, epsilon)2)$. Our lower bound suggests that this quadratic dependence on $1/epsilon$ is inherent for efficient algorithms.
  arXiv  Detail & Related papers  (2023-07-13T18:59:28Z)
• On the average-case complexity of learning output distributions of quantum circuits [55.37943886895049]
  We show that learning the output distributions of brickwork random quantum circuits is average-case hard in the statistical query model. This learning model is widely used as an abstract computational model for most generic learning algorithms.
  arXiv  Detail & Related papers  (2023-05-09T20:53:27Z)
• Quantum Multi-Resolution Measurement with application to Quantum Linear Solver [0.0]
  We propose a quantum multi-resolution measurement (QMRM) that gives a solution with an accuracy $epsilon$ in $O(nlog(1/epsilon))$ measurements. The QMRM computational cost with an accuracy $epsilon$ is smaller than $O(n/epsilon2)$. We also propose an algorithm entitled QMRM-QLS (quantum linear solver) for solving a linear system of equations.
  arXiv  Detail & Related papers  (2023-04-12T16:31:44Z)
• Learning Distributions over Quantum Measurement Outcomes [4.467248776406005]
  Shadow tomography for quantum states provides a sample efficient approach for predicting the properties of quantum systems. We develop an online shadow tomography procedure that solves this problem with high success probability.
  arXiv  Detail & Related papers  (2022-09-07T09:08:58Z)
• Lower bounds for learning quantum states with single-copy measurements [3.2590610391507444]
  We study the problems of quantum tomography and shadow tomography using measurements performed on individual copies of an unknown $d$-dimensional state. In particular, this rigorously establishes the optimality of the folklore Pauli tomography" algorithm in terms of its complexity.
  arXiv  Detail & Related papers  (2022-07-29T02:26:08Z)
• Tight Bounds for Quantum State Certification with Incoherent Measurements [18.566266990940374]
  When $sigma$ is the maximally mixed state $frac1d I_d$, this is known as mixedness testing. We focus on algorithms which use incoherent measurements, i.e. which only measure one copy of $rho$ at a time.
  arXiv  Detail & Related papers  (2022-04-14T17:59:31Z)
• Efficient Bipartite Entanglement Detection Scheme with a Quantum Adversarial Solver [89.80359585967642]
  Proposal reformulates the bipartite entanglement detection as a two-player zero-sum game completed by parameterized quantum circuits. We experimentally implement our protocol on a linear optical network and exhibit its effectiveness to accomplish the bipartite entanglement detection for 5-qubit quantum pure states and 2-qubit quantum mixed states.
  arXiv  Detail & Related papers  (2022-03-15T09:46:45Z)
• Random quantum circuits transform local noise into global white noise [118.18170052022323]
  We study the distribution over measurement outcomes of noisy random quantum circuits in the low-fidelity regime. For local noise that is sufficiently weak and unital, correlations (measured by the linear cross-entropy benchmark) between the output distribution $p_textnoisy$ of a generic noisy circuit instance shrink exponentially. If the noise is incoherent, the output distribution approaches the uniform distribution $p_textunif$ at precisely the same rate.
  arXiv  Detail & Related papers  (2021-11-29T19:26:28Z)
• 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)
• Quantum Algorithms for Simulating the Lattice Schwinger Model [63.18141027763459]
  We give scalable, explicit digital quantum algorithms to simulate the lattice Schwinger model in both NISQ and fault-tolerant settings. In lattice units, we find a Schwinger model on $N/2$ physical sites with coupling constant $x-1/2$ and electric field cutoff $x-1/2Lambda$. We estimate observables which we cost in both the NISQ and fault-tolerant settings by assuming a simple target observable---the mean pair density.
  arXiv  Detail & Related papers  (2020-02-25T19:18:36Z)

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.