Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom

• URL: http://arxiv.org/abs/2209.14530v1
• Date: Thu, 29 Sep 2022 03:34:03 GMT
• Title: Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom
• Authors: Sabee Grewal, Vishnu Iyer, William Kretschmer, Daniel Liang
• Abstract summary: We show that quantum states with "low stabilizer complexity" can be efficiently distinguished from Haar-random. We prove that $omega(log(n))$ $T$-gates are necessary for any Clifford+$T$ circuit to prepare computationally pseudorandom quantum states.
• Score: 1.0323063834827415
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We show that quantum states with "low stabilizer complexity" can be efficiently distinguished from Haar-random. Specifically, given an $n$-qubit pure state $|\psi\rangle$, we give an efficient algorithm that distinguishes whether $|\psi\rangle$ is (i) Haar-random or (ii) a state with stabilizer fidelity at least $\frac{1}{k}$ (i.e., has fidelity at least $\frac{1}{k}$ with some stabilizer state), promised that one of these is the case. With black-box access to $|\psi\rangle$, our algorithm uses $O\!\left( k^{12} \log(1/\delta)\right)$ copies of $|\psi\rangle$ and $O\!\left(n k^{12} \log(1/\delta)\right)$ time to succeed with probability at least $1-\delta$, and, with access to a state preparation unitary for $|\psi\rangle$ (and its inverse), $O\!\left( k^{3} \log(1/\delta)\right)$ queries and $O\!\left(n k^{3} \log(1/\delta)\right)$ time suffice. As a corollary, we prove that $\omega(\log(n))$ $T$-gates are necessary for any Clifford+$T$ circuit to prepare computationally pseudorandom quantum states, a first-of-its-kind lower bound.

Related papers

• Learning junta distributions and quantum junta states, and QAC$^0$ circuits [0.0]
  We consider the problems of learning junta distributions, their quantum counter-part, quantum junta states, and QAC$0$ circuits. We show that they can be learned with error $varepsilon$ in total variation distance. We also prove a lower bound of $Omega(4k+log (n)/varepsilon2)$ copies.
  arXiv  Detail & Related papers  (2024-10-21T09:39:20Z)
• Stabilizer bootstrapping: A recipe for efficient agnostic tomography and magic estimation [16.499689832762765]
  We study the task of tomography: given copies of an unknown $n$-qubit state $rho$ which has fidelity $tau$ with some state in a given class $C$, find a state which has fidelity $ge tau - epsilon$ with $rho$. We give a new framework, stabilizer bootstrapping, for designing computationally efficient protocols for this task, and use this to get new agnostic tomography protocols for the following classes: stabilizer states and discrete product states.
  arXiv  Detail & Related papers  (2024-08-13T15:23:17Z)
• Towards tolerant testing stabilizer states [4.65004369765875]
  We prove an inverse theorem for the Gowers-$3$ norm of states and bounds on stabilizer covering for structured subsets of Paulis. Our proof includes a new definition of Gowers norm for quantum states, an inverse theorem for the Gowers-$3$ norm of states and new bounds on stabilizer covering for structured subsets of Paulis.
  arXiv  Detail & Related papers  (2024-08-12T16:56:33Z)
• Sharp Noisy Binary Search with Monotonic Probabilities [5.563988395126509]
  We revisit the noisy binary search model of Karp and Kleinberg. We produce an algorithm that succeeds with probability $1-delta$ from [ frac1C_tau, varepsilon cdot left(lg n + O(log2/3 n log 1/3 frac1delta + log frac1delta) right.
  arXiv  Detail & Related papers  (2023-11-01T20:45:13Z)
• Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
  We study iterative methods based on Krylov subspaces for low-rank approximation under any Schatten-$p$ norm. Our main result is an algorithm that uses only $tildeO(k/sqrtepsilon)$ matrix-vector products.
  arXiv  Detail & Related papers  (2022-02-10T16:10:41Z)
• Learning low-degree functions from a logarithmic number of random queries [77.34726150561087]
  We prove that for any integer $ninmathbbN$, $din1,ldots,n$ and any $varepsilon,deltain(0,1)$, a bounded function $f:-1,1nto[-1,1]$ of degree at most $d$ can be learned.
  arXiv  Detail & Related papers  (2021-09-21T13:19:04Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
  arXiv  Detail & Related papers  (2020-08-24T06:50:57Z)
• Fast digital methods for adiabatic state preparation [0.0]
  We present a quantum algorithm for adiabatic state preparation on a gate-based quantum computer, with complexity polylogarithmic in the inverse error.
  arXiv  Detail & Related papers  (2020-04-08T18:00:01Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  We output a distribution from $mathcalQ$ whose total variation distance to $p$ is comparable to the best such distribution. We show that the constraint of local differential privacy incurs an exponential increase in cost. Our algorithms result in exponential improvements on the round complexity of previous methods.
  arXiv  Detail & Related papers  (2020-02-21T18:30:48Z)
• Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
  We prove tight lower bounds for the following variant of the counting problem considered by Aaronson, Kothari, Kretschmer, and Thaler ( 2020) The task is to distinguish whether an input set $xsubseteq [n]$ has size either $k$ or $k'=(1+varepsilon)k$.
  arXiv  Detail & Related papers  (2020-02-17T10:53:50Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  We exploit the finite noise structure of finite sums to derive a matching $O(n2)$-upper bound under the global oracle model. Following a similar approach, we propose a novel adaptation of SVRG which is both emphcompatible with oracles, and achieves complexity bounds of $tildeO(n2+nsqrtL/mu)log (1/epsilon)$ and $O(nsqrtL/epsilon)$, for $mu>0$ and $mu=0$
  arXiv  Detail & Related papers  (2020-02-09T03:39:46Z)

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.