Published in: LIPIcs, Volume 266, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)
William Kretschmer. Quantum Mass Production Theorems. In 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 266, pp. 10:1-10:11, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{kretschmer:LIPIcs.TQC.2023.10, author = {Kretschmer, William}, title = {{Quantum Mass Production Theorems}}, booktitle = {18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)}, pages = {10:1--10:11}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2023.10}, URN = {urn:nbn:de:0030-drops-183206}, doi = {10.4230/LIPIcs.TQC.2023.10}, annote = {Keywords: mass production, quantum circuit synthesis, quantum circuit complexity} }
Published in: LIPIcs, Volume 266, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)
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)
@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.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} }
Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Anand Natarajan and Chinmay Nirkhe. A Distribution Testing Oracle Separating QMA and QCMA. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 22:1-22:27, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{natarajan_et_al:LIPIcs.CCC.2023.22, author = {Natarajan, Anand and Nirkhe, Chinmay}, title = {{A Distribution Testing Oracle Separating QMA and QCMA}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {22:1--22:27}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-282-2}, ISSN = {1868-8969}, year = {2023}, volume = {264}, editor = {Ta-Shma, Amnon}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.22}, URN = {urn:nbn:de:0030-drops-182928}, doi = {10.4230/LIPIcs.CCC.2023.22}, annote = {Keywords: quantum non-determinism, complexity theory} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Zvika Brakerski, Ran Canetti, and Luowen Qian. On the Computational Hardness Needed for Quantum Cryptography. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 24:1-24:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{brakerski_et_al:LIPIcs.ITCS.2023.24, author = {Brakerski, Zvika and Canetti, Ran and Qian, Luowen}, title = {{On the Computational Hardness Needed for Quantum Cryptography}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {24:1--24:21}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.24}, URN = {urn:nbn:de:0030-drops-175278}, doi = {10.4230/LIPIcs.ITCS.2023.24}, annote = {Keywords: quantum cryptography, efi, commitment scheme, oblivious transfer, zero knowledge, secure multiparty computation} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
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)
@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.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} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Scott Aaronson, DeVon Ingram, and William Kretschmer. The Acrobatics of BQP. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 20:1-20:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{aaronson_et_al:LIPIcs.CCC.2022.20, author = {Aaronson, Scott and Ingram, DeVon and Kretschmer, William}, title = {{The Acrobatics of BQP}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {20:1--20:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-241-9}, ISSN = {1868-8969}, year = {2022}, volume = {234}, editor = {Lovett, Shachar}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.20}, URN = {urn:nbn:de:0030-drops-165820}, doi = {10.4230/LIPIcs.CCC.2022.20}, annote = {Keywords: BQP, Forrelation, oracle separations, Polynomial Hierarchy, query complexity} }
Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)
Scott Aaronson. BQP After 28 Years (Invited Talk). In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, p. 1:1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{aaronson:LIPIcs.FSTTCS.2021.1, author = {Aaronson, Scott}, title = {{BQP After 28 Years}}, booktitle = {41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)}, pages = {1:1--1:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-215-0}, ISSN = {1868-8969}, year = {2021}, volume = {213}, editor = {Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.1}, URN = {urn:nbn:de:0030-drops-155124}, doi = {10.4230/LIPIcs.FSTTCS.2021.1}, annote = {Keywords: quantum computing, complexity theory, oracle separations, circuit lower bounds} }
Published in: LIPIcs, Volume 197, 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021)
William Kretschmer. Quantum Pseudorandomness and Classical Complexity. In 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 197, pp. 2:1-2:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@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/entities/document/10.4230/LIPIcs.TQC.2021.2}, URN = {urn:nbn:de:0030-drops-139975}, doi = {10.4230/LIPIcs.TQC.2021.2}, annote = {Keywords: pseudorandom quantum states, quantum Merlin-Arthur} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
William Kretschmer. The Quantum Supremacy Tsirelson Inequality. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 13:1-13:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{kretschmer:LIPIcs.ITCS.2021.13, author = {Kretschmer, William}, title = {{The Quantum Supremacy Tsirelson Inequality}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {13:1--13:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-177-1}, ISSN = {1868-8969}, year = {2021}, volume = {185}, editor = {Lee, James R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.13}, URN = {urn:nbn:de:0030-drops-135524}, doi = {10.4230/LIPIcs.ITCS.2021.13}, annote = {Keywords: quantum supremacy, quantum query complexity, random circuit sampling} }
Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)
Scott Aaronson, Robin Kothari, William Kretschmer, and Justin Thaler. Quantum Lower Bounds for Approximate Counting via Laurent Polynomials. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 7:1-7:47, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{aaronson_et_al:LIPIcs.CCC.2020.7, author = {Aaronson, Scott and Kothari, Robin and Kretschmer, William and Thaler, Justin}, title = {{Quantum Lower Bounds for Approximate Counting via Laurent Polynomials}}, booktitle = {35th Computational Complexity Conference (CCC 2020)}, pages = {7:1--7:47}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-156-6}, ISSN = {1868-8969}, year = {2020}, volume = {169}, editor = {Saraf, Shubhangi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.7}, URN = {urn:nbn:de:0030-drops-125593}, doi = {10.4230/LIPIcs.CCC.2020.7}, annote = {Keywords: Approximate counting, Laurent polynomials, QSampling, query complexity} }
Feedback for Dagstuhl Publishing