License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.TQC.2021.2
URN: urn:nbn:de:0030-drops-139975
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13997/
Go to the corresponding LIPIcs Volume Portal

Kretschmer, William

Quantum Pseudorandomness and Classical Complexity

pdf-format:
LIPIcs-TQC-2021-2.pdf (0.8 MB)

Abstract

We construct a quantum oracle relative to which BQP = QMA but cryptographic pseudorandom quantum states and pseudorandom unitary transformations exist, a counterintuitive result in light of the fact that pseudorandom states can be "broken" by quantum Merlin-Arthur adversaries. We explain how this nuance arises as the result of a distinction between algorithms that operate on quantum and classical inputs. On the other hand, we show that some computational complexity assumption is needed to construct pseudorandom states, by proving that pseudorandom states do not exist if BQP = PP. We discuss implications of these results for cryptography, complexity theory, and quantum tomography.

BibTeX - Entry

@InProceedings{kretschmer:LIPIcs.TQC.2021.2,
  author =	{Kretschmer, William},
  title =	{{Quantum Pseudorandomness and Classical Complexity}},
  booktitle =	{16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021)},
  pages =	{2:1--2:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-198-6},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{197},
  editor =	{Hsieh, Min-Hsiu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/13997},
  URN =		{urn:nbn:de:0030-drops-139975},
  doi =		{10.4230/LIPIcs.TQC.2021.2},
  annote =	{Keywords: pseudorandom quantum states, quantum Merlin-Arthur}
}

Keywords: pseudorandom quantum states, quantum Merlin-Arthur
Collection: 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021)
Issue Date: 2021
Date of publication: 22.06.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI