Eliminating Intermediate Measurements using Pseudorandom Generators
- URL: http://arxiv.org/abs/2106.11877v2
- Date: Sat, 28 Aug 2021 02:43:13 GMT
- Title: Eliminating Intermediate Measurements using Pseudorandom Generators
- Authors: Uma Girish, Ran Raz
- Abstract summary: We show that quantum algorithms of time $T$ and space $Sge log T$ can be simulated by quantum algorithms of time $T cdot mathrmpoly (S)$ and space $ O(Scdot log T)$ with unitary operations and without intermediate measurements.
- Score: 1.218340575383456
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We show that quantum algorithms of time $T$ and space $S\ge \log T$ with
unitary operations and intermediate measurements can be simulated by quantum
algorithms of time $T \cdot \mathrm{poly} (S)$ and space $ {O}(S\cdot \log T)$
with unitary operations and without intermediate measurements. The best results
prior to this work required either $\Omega(T)$ space (by the deferred
measurement principle) or $\mathrm{poly}(2^S)$ time [FR21,GRZ21]. Our result is
thus a time-efficient and space-efficient simulation of algorithms with unitary
operations and intermediate measurements by algorithms with unitary operations
and without intermediate measurements.
To prove our result, we study pseudorandom generators for quantum
space-bounded algorithms. We show that (an instance of) the INW pseudorandom
generator for classical space-bounded algorithms [INW94] also fools quantum
space-bounded algorithms. More precisely, we show that for quantum
space-bounded algorithms that have access to a read-once tape consisting of
random bits, the final state of the algorithm when the random bits are drawn
from the uniform distribution is nearly identical to the final state when the
random bits are drawn using the INW pseudorandom generator. This result applies
to general quantum algorithms which can apply unitary operations, perform
intermediate measurements and reset qubits.
Related papers
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP)
We generalize the SDP-inspired quantum algorithm to sum-of-squares.
Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
arXiv Detail & Related papers (2024-08-14T19:04:13Z) - 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) - Fast Optimal Locally Private Mean Estimation via Random Projections [58.603579803010796]
We study the problem of locally private mean estimation of high-dimensional vectors in the Euclidean ball.
We propose a new algorithmic framework, ProjUnit, for private mean estimation.
Our framework is deceptively simple: each randomizer projects its input to a random low-dimensional subspace, normalizes the result, and then runs an optimal algorithm.
arXiv Detail & Related papers (2023-06-07T14:07:35Z) - An adaptive Bayesian quantum algorithm for phase estimation [0.0]
We present a coherence-based phase-estimation algorithm which can achieve the optimal quadratic scaling in the mean absolute error and the mean squared error.
In the presence of noise, our algorithm produces errors that approach the theoretical lower bound.
arXiv Detail & Related papers (2023-03-02T19:00:01Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
General tools for designing efficient private estimation algorithms.
First efficient $(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery.
arXiv Detail & Related papers (2023-01-11T09:12:28Z) - Learning to predict arbitrary quantum processes [7.69390398476646]
We present an efficient machine learning (ML) algorithm for predicting any unknown quantum process over $n$ qubits.
Our results highlight the potential for ML models to predict the output of complex quantum dynamics much faster than the time needed to run the process itself.
arXiv Detail & Related papers (2022-10-26T17:52:59Z) - A single $T$-gate makes distribution learning hard [56.045224655472865]
This work provides an extensive characterization of the learnability of the output distributions of local quantum circuits.
We show that for a wide variety of the most practically relevant learning algorithms -- including hybrid-quantum classical algorithms -- even the generative modelling problem associated with depth $d=omega(log(n))$ Clifford circuits is hard.
arXiv Detail & Related papers (2022-07-07T08:04:15Z) - How to simulate quantum measurement without computing marginals [3.222802562733787]
We describe and analyze algorithms for classically computation measurement of an $n$-qubit quantum state $psi$ in the standard basis.
Our algorithms reduce the sampling task to computing poly(n)$ amplitudes of $n$-qubit states.
arXiv Detail & Related papers (2021-12-15T21:44:05Z) - Quantum Logspace Algorithm for Powering Matrices with Bounded Norm [7.510385608531827]
We give a quantum logspace algorithm for powering contraction matrices, that is, with spectral norm at most1.
The algorithm applies only unitary operators, without intermediate measurements.
This shows that the deferred-measurement principle, a fundamental principle of quantum computing, applies also for quantum logspace algorithms.
arXiv Detail & Related papers (2020-06-08T19:01:04Z) - Quantum Relief Algorithm [12.599184944451833]
Relief algorithm is a feature selection algorithm used in binary classification proposed by Kira and Rendell.
A quantum feature selection algorithm based on Relief algorithm, also called quantum Relief algorithm, is proposed.
arXiv Detail & Related papers (2020-02-01T10:18:34Z) - Efficient classical simulation of random shallow 2D quantum circuits [104.50546079040298]
Random quantum circuits are commonly viewed as hard to simulate classically.
We show that approximate simulation of typical instances is almost as hard as exact simulation.
We also conjecture that sufficiently shallow random circuits are efficiently simulable more generally.
arXiv Detail & Related papers (2019-12-31T19:00:00Z)
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.