Pseudoentanglement Ain't Cheap

• URL: http://arxiv.org/abs/2404.00126v2
• Date: Fri, 12 Apr 2024 03:09:38 GMT
• Title: Pseudoentanglement Ain't Cheap
• Authors: Sabee Grewal, Vishnu Iyer, William Kretschmer, Daniel Liang,
• Abstract summary: We show that any pseudoentangled state ensemble with a gap of $t$ bits of entropy requires $Omega(t)$ non-Clifford gates to prepare. This is tight up to polylogarithmic factors if linear-time-secure pseudorandom functions exist.
• Score: 0.43123403062068827
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We show that any pseudoentangled state ensemble with a gap of $t$ bits of entropy requires $\Omega(t)$ non-Clifford gates to prepare. This bound is tight up to polylogarithmic factors if linear-time quantum-secure pseudorandom functions exist. Our result follows from a polynomial-time algorithm to estimate the entanglement entropy of a quantum state across any cut of qubits. When run on an $n$-qubit state that is stabilized by at least $2^{n-t}$ Pauli operators, our algorithm produces an estimate that is within an additive factor of $\frac{t}{2}$ bits of the true entanglement entropy.

Related papers

• Measuring quantum relative entropy with finite-size effect [53.64687146666141]
  We study the estimation of relative entropy $D(rho|sigma)$ when $sigma$ is known. Our estimator attains the Cram'er-Rao type bound when the dimension $d$ is fixed.
  arXiv  Detail & Related papers  (2024-06-25T06:07:20Z)
• 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)
• Classical simulation of peaked shallow quantum circuits [2.6089354079273512]
  We describe an algorithm with quasipolynomial runtime $nO(logn)$ that samples from the output distribution of a peaked constant-depth circuit. Our algorithms can be used to estimate output probabilities of shallow circuits to within a given inverse-polynomial additive error.
  arXiv  Detail & Related papers  (2023-09-15T14:01:13Z)
• Efficient Quantum State Synthesis with One Query [0.0]
  We present a time analogue quantum algorithm making a single query (in superposition) to a classical oracle. We prove that every $n$-qubit state can be constructed to within 0.01 error by an $On/n)$-size circuit over an appropriate finite gate set.
  arXiv  Detail & Related papers  (2023-06-02T17:49:35Z)
• 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)
• Fast Rates for Maximum Entropy Exploration [52.946307632704645]
  We address the challenge of exploration in reinforcement learning (RL) when the agent operates in an unknown environment with sparse or no rewards. We study the maximum entropy exploration problem two different types. For visitation entropy, we propose a game-theoretic algorithm that has $widetildemathcalO(H3S2A/varepsilon2)$ sample complexity. For the trajectory entropy, we propose a simple algorithm that has a sample of complexity of order $widetildemathcalO(mathrmpoly(S,
  arXiv  Detail & Related papers  (2023-03-14T16:51:14Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems. We show that the algorithm finds the optimal solution in time $O*(2(0.5-c)n)$ for an $n$-independent constant $c$. We also show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case.
  arXiv  Detail & Related papers  (2022-12-03T02:45:23Z)
• A Law of Robustness beyond Isoperimetry [84.33752026418045]
  We prove a Lipschitzness lower bound $Omega(sqrtn/p)$ of robustness of interpolating neural network parameters on arbitrary distributions. We then show the potential benefit of overparametrization for smooth data when $n=mathrmpoly(d)$. We disprove the potential existence of an $O(1)$-Lipschitz robust interpolating function when $n=exp(omega(d))$.
  arXiv  Detail & Related papers  (2022-02-23T16:10:23Z)
• Sublinear quantum algorithms for estimating von Neumann entropy [18.30551855632791]
  We study the problem of obtaining estimates to within a multiplicative factor $gamma>1$ of the Shannon entropy of probability distributions and the von Neumann entropy of mixed quantum states. We work with the quantum purified query access model, which can handle both classical probability distributions and mixed quantum states, and is the most general input model considered in the literature.
  arXiv  Detail & Related papers  (2021-11-22T12:00:45Z)
• Quasi-polynomial time algorithms for free quantum games in bounded dimension [11.56707165033]
  We give a semidefinite program of size $exp(mathcalObig(T12(log2(AT)+log(Q)log(AT))/epsilon2big)) to compute additive $epsilon$-approximations on the values of two-player free games. We make a connection to the quantum separability problem and employ improved multipartite quantum de Finetti theorems with linear constraints.
  arXiv  Detail & Related papers  (2020-05-18T16:55:08Z)
• 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)

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.