Related papers: Learning t-doped stabilizer states

Learning t-doped stabilizer states

URL: http://arxiv.org/abs/2305.15398v6
Date: Tue, 21 May 2024 19:50:58 GMT
Title: Learning t-doped stabilizer states
Authors: Lorenzo Leone, Salvatore F. E. Oliviero, Alioscia Hamma,
Abstract summary: We present a learning algorithm aimed at learning states obtained from computational basis states by Clifford circuits doped with a finite number $t$ of $T$-gates. The algorithm learns an exact tomographic description of $t$-doped stabilizer states in terms of Pauli observables.
Score: 0.0
License: http://creativecommons.org/licenses/by/4.0/
Abstract: In this paper, we present a learning algorithm aimed at learning states obtained from computational basis states by Clifford circuits doped with a finite number $t$ of $T$-gates. The algorithm learns an exact tomographic description of $t$-doped stabilizer states in terms of Pauli observables. This is possible because such states are countable and form a discrete set. To tackle the problem, we introduce a novel algebraic framework for $t$-doped stabilizer states, which extends beyond $T$-gates and includes doping with any kind of local non-Clifford gate. The algorithm requires resources of complexity $\text{poly}(n,2^t)$ and exhibits an exponentially small probability of failure.

Related papers

Quantum State Learning Implies Circuit Lower Bounds [2.2667044928324747]
We establish connections between state tomography, pseudorandomness, quantum state, circuit lower bounds. We show that even slightly non-trivial quantum state tomography algorithms would lead to new statements about quantum state synthesis.
arXiv Detail & Related papers (2024-05-16T16:46:27Z)
Agnostic Tomography of Stabilizer Product States [0.43123403062068827]
We give an efficient agnostic tomography algorithm for the class $mathcalC$ of $n$-qubit stabilizer product states. We output a succinct description of a state that approximates at least as well as any state in $mathcalC$.
arXiv Detail & Related papers (2024-04-04T21:39:47Z)
Pseudorandom and Pseudoentangled States from Subset States [49.74460522523316]
A subset state with respect to $S$, a subset of the computational basis, is [ frac1sqrt|S|sum_iin S |irangle. We show that for any fixed subset size $|S|=s$ such that $s = 2n/omega(mathrmpoly(n))$ and $s=omega(mathrmpoly(n))$, a random subset state is information-theoretically indistinguishable from a Haar random state even provided
arXiv Detail & Related papers (2023-12-23T15:52:46Z)
Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
arXiv Detail & Related papers (2023-07-24T14:37:22Z)
Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates [0.43123403062068827]
We give a pair of algorithms that efficiently learn a quantum state prepared by Clifford gates and $O(log n)$ non-Clifford gates. Specifically, for an $n$-qubit state $|psirangle$ prepared with at most $t$ non-Clifford gates, our algorithms use $mathsfpoly(n,2t,1/varepsilon)$ time and copies of $|psirangle$ to learn $|psirangle$ to trace distance at most gates.
arXiv Detail & Related papers (2023-05-22T18:49:52Z)
Improved Stabilizer Estimation via Bell Difference Sampling [0.43123403062068827]
We study the complexity of learning quantum states in various models with respect to the stabilizer formalism. We prove that $Omega(n)$ $T$gates are necessary for any Clifford+$T$ circuit to prepare pseudorandom quantum states. We show that a modification of the above algorithm runs in time.
arXiv Detail & Related papers (2023-04-27T01:58:28Z)
Layered State Discovery for Incremental Autonomous Exploration [106.37656068276901]
Layered Autonomous Exploration (LAE) is a novel algorithm for AX that attains a sample complexity of $tildemathcalO(LSrightarrow_LAln12(Srightarrow_LAln12(Srightarrow_LAln12(Srightarrow_LAln12(Srightar row_LAln12(Srightarrow_LAln12
arXiv Detail & Related papers (2023-02-07T22:58:12Z)
Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Path [106.37656068276902]
We study the sample complexity of learning an $epsilon$-optimal policy in the Shortest Path (SSP) problem. We derive complexity bounds when the learner has access to a generative model. We show that there exists a worst-case SSP instance with $S$ states, $A$ actions, minimum cost $c_min$, and maximum expected cost of the optimal policy over all states $B_star$.
arXiv Detail & Related papers (2022-10-10T18:34:32Z)
Minimal Expected Regret in Linear Quadratic Control [79.81807680370677]
We devise an online learning algorithm and provide guarantees on its expected regret. This regret at time $T$ is upper bounded (i) by $widetildeO((d_u+d_x)sqrtd_xT)$ when $A$ and $B$ are unknown.
arXiv Detail & Related papers (2021-09-29T14:07:21Z)
Learning quantum circuits of some $T$ gates [10.609715843964263]
It has been unknown how to handle circuits beyond the Clifford group. We show that the output state of a $T$-depth one circuit textitof full $T$-rank can be represented by a stabilizer pseudomixture.
arXiv Detail & Related papers (2021-06-23T16:43:01Z)
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)

This list is automatically generated from the titles and abstracts of the papers in this site.