2 Search Results for "Fitzsimons, Joseph F."

Document
DOI: 10.4230/LIPIcs.CCC.2025.12
New Lower-Bounds for Quantum Computation with Non-Collapsing Measurements

Authors: David Miloschewsky and Supartha Podder

Published in: LIPIcs, Volume 339, 40th Computational Complexity Conference (CCC 2025)

Abstract
Aaronson, Bouland, Fitzsimons and Lee [Scott Aaronson et al., 2014] introduced the complexity class PDQP (which was original labeled naCQP), an alteration of BQP enhanced with the ability to obtain non-collapsing measurements, samples of quantum states without collapsing them. Although SZK ⊆ PDQP, it still requires Ω(N^(1/4)) queries to solve unstructured search. We formulate an alternative equivalent definition of PDQP, which we use to prove the positive weighted adversary lower-bounding method, establishing multiple tighter bounds and a trade-off between queries and non-collapsing measurements. We utilize the technique in order to analyze the query complexity of the well-studied majority and element distinctness problems. Additionally, we prove a tight Θ(N^(1/3)) bound on search. Furthermore, we use the lower-bound to explore PDQP under query restrictions, finding that when combined with non-adaptive queries, we limit the speed-up in several cases.
Cite as

David Miloschewsky and Supartha Podder. New Lower-Bounds for Quantum Computation with Non-Collapsing Measurements. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 12:1-12:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{miloschewsky_et_al:LIPIcs.CCC.2025.12,
  author =	{Miloschewsky, David and Podder, Supartha},
  title =	{{New Lower-Bounds for Quantum Computation with Non-Collapsing Measurements}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{12:1--12:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-379-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{339},
  editor =	{Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2025.12},
  URN =		{urn:nbn:de:0030-drops-237067},
  doi =		{10.4230/LIPIcs.CCC.2025.12},
  annote =	{Keywords: Non-collapsing measurements, Quantum lower-bounds, Quantum adversary method}
}
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 Type
  • 2 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2018

  • Refine by Author
  • 1 Bouland, Adam
  • 1 Fitzsimons, Joseph F.
  • 1 Koh, Dax Enshan
  • 1 Miloschewsky, David
  • 1 Podder, Supartha

  • Refine by Series/Journal
  • 2 LIPIcs

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

  • Refine by Keyword
  • 1 Non-collapsing measurements
  • 1 Quantum adversary method
  • 1 Quantum lower-bounds
  • 1 gate set classification
  • 1 polynomial hierarchy
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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