2 Search Results for "Iyer, Vishnu"

Document
DOI: 10.4230/LIPIcs.ITCS.2023.64
Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom

Authors: Sabee Grewal, Vishnu Iyer, William Kretschmer, and Daniel Liang

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
We show that quantum states with "low stabilizer complexity" can be efficiently distinguished from Haar-random. Specifically, given an n-qubit pure state |ψ⟩, we give an efficient algorithm that distinguishes whether |ψ⟩ is (i) Haar-random or (ii) a state with stabilizer fidelity at least 1/k (i.e., has fidelity at least 1/k with some stabilizer state), promised that one of these is the case. With black-box access to |ψ⟩, our algorithm uses O(k^{12} log(1/δ)) copies of |ψ⟩ and O(n k^{12} log(1/δ)) time to succeed with probability at least 1-δ, and, with access to a state preparation unitary for |ψ⟩ (and its inverse), O(k³ log(1/δ)) queries and O(n k³ log(1/δ)) time suffice. As a corollary, we prove that ω(log(n)) T-gates are necessary for any Clifford+T circuit to prepare computationally pseudorandom quantum states, a first-of-its-kind lower bound.
Cite as

Sabee Grewal, Vishnu Iyer, William Kretschmer, and Daniel Liang. Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 64:1-64:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{grewal_et_al:LIPIcs.ITCS.2023.64,
  author =	{Grewal, Sabee and Iyer, Vishnu and Kretschmer, William and Liang, Daniel},
  title =	{{Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{64:1--64:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.64},
  URN =		{urn:nbn:de:0030-drops-175670},
  doi =		{10.4230/LIPIcs.ITCS.2023.64},
  annote =	{Keywords: Pseudorandom quantum states, Clifford + T, Haar random, Bell sampling, stabilizer formalism, stabilizer extent, stabilizer fidelity, learning theory, complexity theory}
}
Document
DOI: 10.4230/LIPIcs.CCC.2021.24
Junta Distance Approximation with Sub-Exponential Queries

Authors: Vishnu Iyer, Avishay Tal, and Michael Whitmeyer

Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)

Abstract
Leveraging tools of De, Mossel, and Neeman [FOCS, 2019], we show two different results pertaining to the tolerant testing of juntas. Given black-box access to a Boolean function f:{±1}ⁿ → {±1}: 1) We give a poly(k, 1/(ε)) query algorithm that distinguishes between functions that are γ-close to k-juntas and (γ+ε)-far from k'-juntas, where k' = O(k/(ε²)). 2) In the non-relaxed setting, we extend our ideas to give a 2^{Õ(√{k/ε})} (adaptive) query algorithm that distinguishes between functions that are γ-close to k-juntas and (γ+ε)-far from k-juntas. To the best of our knowledge, this is the first subexponential-in-k query algorithm for approximating the distance of f to being a k-junta (previous results of Blais, Canonne, Eden, Levi, and Ron [SODA, 2018] and De, Mossel, and Neeman [FOCS, 2019] required exponentially many queries in k). Our techniques are Fourier analytical and make use of the notion of "normalized influences" that was introduced by Talagrand [Michel Talagrand, 1994].
Cite as

Vishnu Iyer, Avishay Tal, and Michael Whitmeyer. Junta Distance Approximation with Sub-Exponential Queries. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 24:1-24:38, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{iyer_et_al:LIPIcs.CCC.2021.24,
  author =	{Iyer, Vishnu and Tal, Avishay and Whitmeyer, Michael},
  title =	{{Junta Distance Approximation with Sub-Exponential Queries}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{24:1--24:38},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-193-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{200},
  editor =	{Kabanets, Valentine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.24},
  URN =		{urn:nbn:de:0030-drops-142988},
  doi =		{10.4230/LIPIcs.CCC.2021.24},
  annote =	{Keywords: Algorithms, Complexity Theory, Fourier Analysis, Juntas, Normalized Influence, Property Testing, Tolerant Property Testing}
}
  • Refine by Author
  • 2 Iyer, Vishnu
  • 1 Grewal, Sabee
  • 1 Kretschmer, William
  • 1 Liang, Daniel
  • 1 Tal, Avishay
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Computational complexity and cryptography
  • 1 Theory of computation → Quantum complexity theory

  • Refine by Keyword
  • 1 Algorithms
  • 1 Bell sampling
  • 1 Clifford + T
  • 1 Complexity Theory
  • 1 Fourier Analysis
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2021
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact