More Optimal Simulation of Universal Quantum Computers
- URL: http://arxiv.org/abs/2202.01233v2
- Date: Tue, 26 Apr 2022 19:51:54 GMT
- Title: More Optimal Simulation of Universal Quantum Computers
- Authors: Lucas Kocia, Genele Tulloch
- Abstract summary: Worst-case sampling cost has plateaued at $le(2+sqrt2)xi_t delta-1$ in the limit that $t rightarrow infty$.
We reduce this prefactor 68-fold by a leading-order reduction in $t$ through correlated sampling.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Validating whether a quantum device confers a computational advantage often
requires classical simulation of its outcomes. The worst-case sampling cost of
$L_1$-norm based simulation has plateaued at $\le(2+\sqrt{2})\xi_t \delta^{-1}$
in the limit that $t \rightarrow \infty$, where $\delta$ is the additive error
and $\xi_t$ is the stabilizer extent of a $t$-qubit magic state. We reduce this
prefactor 68-fold by a leading-order reduction in $t$ through correlated
sampling. The result exceeds even the average-case of the prior
state-of-the-art and current simulators accurate to multiplicative error.
Numerical demonstrations support our proofs. The technique can be applied
broadly to reduce the cost of $L_1$ minimization.
Related papers
- Theoretical limits of descending $\ell_0$ sparse-regression ML algorithms [0.0]
We develop a generic analytical program for studying performance of the emphmaximum-likelihood (ML) decoding.
Key ML performance parameter, the residual emphroot mean square error ($textbfRMSE$) is uncovered to exhibit the so-called emphphase-transition (PT) phenomenon.
Concrete implementation and practical relevance of the Fl RDT typically rely on the ability to conduct a sizeable set of the underlying numerical evaluations.
arXiv Detail & Related papers (2024-10-10T06:33:41Z) - 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) - Minimax Optimal Quantization of Linear Models: Information-Theoretic
Limits and Efficient Algorithms [59.724977092582535]
We consider the problem of quantizing a linear model learned from measurements.
We derive an information-theoretic lower bound for the minimax risk under this setting.
We show that our method and upper-bounds can be extended for two-layer ReLU neural networks.
arXiv Detail & Related papers (2022-02-23T02:39:04Z) - 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) - Improved Weak Simulation of Universal Quantum Circuits by Correlated
$L_1$ Sampling [0.0]
Weak simulation is often called weak simulation and is a way to determine when they confer a quantum advantage.
We constructively tighten the upper bound on the worst-case $L_$ norm sampling cost to next order in $t$ from $mathcal O(xit delta-2)$.
This is the first weak simulation algorithm that has lowered this bound's dependence on finite $t$ in the worst-case to our knowledge.
arXiv Detail & Related papers (2021-04-15T05:50:11Z) - Improved Sample Complexity for Incremental Autonomous Exploration in
MDPs [132.88757893161699]
We learn the set of $epsilon$-optimal goal-conditioned policies attaining all states that are incrementally reachable within $L$ steps.
DisCo is the first algorithm that can return an $epsilon/c_min$-optimal policy for any cost-sensitive shortest-path problem.
arXiv Detail & Related papers (2020-12-29T14:06:09Z) - Early fault-tolerant simulations of the Hubbard model [3.988614978933934]
Simulation of the Hubbard model is a leading candidate for the first useful applications of a fault-tolerant quantum computer.
We present a new analytic approach to bounding the simulation error due to Trotterization that provides much tighter bounds for the split-operator FFFT method.
We find there is a potentially useful application for fault-tolerant quantum computers using around one million Toffoli gates.
arXiv Detail & Related papers (2020-12-16T20:07:54Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
We study the problem of high-dimensional robust linear regression where a learner is given access to $n$ samples from the generative model $Y = langle X,w* rangle + epsilon$
We propose estimators for this problem under two settings: (i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance and (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
arXiv Detail & Related papers (2020-07-16T06:44:44Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
Asynchronous Q-learning aims to learn the optimal action-value function (or Q-function) of a Markov decision process (MDP)
We show that the number of samples needed to yield an entrywise $varepsilon$-accurate estimate of the Q-function is at most on the order of $frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$ up to some logarithmic factor.
arXiv Detail & Related papers (2020-06-04T17:51:00Z) - 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.