2 Search Results for "Koh, Dax Enshan"

Document
DOI: 10.4230/LIPIcs.TQC.2023.12
Efficient Tomography of Non-Interacting-Fermion States

Authors: Scott Aaronson and Sabee Grewal

Published in: LIPIcs, Volume 266, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)

Abstract
We give an efficient algorithm that learns a non-interacting-fermion state, given copies of the state. For a system of n non-interacting fermions and m modes, we show that O(m³ n² log(1/δ) / ε⁴) copies of the input state and O(m⁴ n² log(1/δ)/ ε⁴) time are sufficient to learn the state to trace distance at most ε with probability at least 1 - δ. Our algorithm empirically estimates one-mode correlations in O(m) different measurement bases and uses them to reconstruct a succinct description of the entire state efficiently.
Cite as

Scott Aaronson and Sabee Grewal. Efficient Tomography of Non-Interacting-Fermion States. In 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 266, pp. 12:1-12:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{aaronson_et_al:LIPIcs.TQC.2023.12,
  author =	{Aaronson, Scott and Grewal, Sabee},
  title =	{{Efficient Tomography of Non-Interacting-Fermion States}},
  booktitle =	{18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)},
  pages =	{12:1--12:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-283-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{266},
  editor =	{Fawzi, Omar and Walter, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2023.12},
  URN =		{urn:nbn:de:0030-drops-183222},
  doi =		{10.4230/LIPIcs.TQC.2023.12},
  annote =	{Keywords: free-fermions, Gaussian fermions, non-interacting fermions, quantum state tomography, efficient tomography}
}
Document
DOI: 10.4230/LIPIcs.CCC.2018.21
Complexity Classification of Conjugated Clifford Circuits

Authors: Adam Bouland, Joseph F. Fitzsimons, and Dax Enshan Koh

Published in: LIPIcs, Volume 102, 33rd Computational Complexity Conference (CCC 2018)

Abstract
Clifford circuits - i.e. circuits composed of only CNOT, Hadamard, and pi/4 phase gates - play a central role in the study of quantum computation. However, their computational power is limited: a well-known result of Gottesman and Knill states that Clifford circuits are efficiently classically simulable. We show that in contrast, "conjugated Clifford circuits" (CCCs) - where one additionally conjugates every qubit by the same one-qubit gate U - can perform hard sampling tasks. In particular, we fully classify the computational power of CCCs by showing that essentially any non-Clifford conjugating unitary U can give rise to sampling tasks which cannot be efficiently classically simulated to constant multiplicative error, unless the polynomial hierarchy collapses. Furthermore, by standard techniques, this hardness result can be extended to allow for the more realistic model of constant additive error, under a plausible complexity-theoretic conjecture. This work can be seen as progress towards classifying the computational power of all restricted quantum gate sets.
Cite as

Adam Bouland, Joseph F. Fitzsimons, and Dax Enshan Koh. Complexity Classification of Conjugated Clifford Circuits. In 33rd Computational Complexity Conference (CCC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 102, pp. 21:1-21:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bouland_et_al:LIPIcs.CCC.2018.21,
  author =	{Bouland, Adam and Fitzsimons, Joseph F. and Koh, Dax Enshan},
  title =	{{Complexity Classification of Conjugated Clifford Circuits}},
  booktitle =	{33rd Computational Complexity Conference (CCC 2018)},
  pages =	{21:1--21:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-069-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{102},
  editor =	{Servedio, Rocco A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2018.21},
  URN =		{urn:nbn:de:0030-drops-88677},
  doi =		{10.4230/LIPIcs.CCC.2018.21},
  annote =	{Keywords: gate set classification, quantum advantage, sampling problems, polynomial hierarchy}
}
  • Refine by Author
  • 1 Aaronson, Scott
  • 1 Bouland, Adam
  • 1 Fitzsimons, Joseph F.
  • 1 Grewal, Sabee
  • 1 Koh, Dax Enshan

  • Refine by Classification
  • 2 Theory of computation → Quantum complexity theory
  • 1 Mathematics of computing → Probabilistic inference problems
  • 1 Theory of computation → Computational complexity and cryptography
  • 1 Theory of computation → Quantum computation theory
  • 1 Theory of computation → Quantum information theory

  • Refine by Keyword
  • 1 Gaussian fermions
  • 1 efficient tomography
  • 1 free-fermions
  • 1 gate set classification
  • 1 non-interacting fermions
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2018
  • 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