Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Adam Bouland, Bill Fefferman, Soumik Ghosh, Tony Metger, Umesh Vazirani, Chenyi Zhang, and Zixin Zhou. Public-Key Pseudoentanglement and the Hardness of Learning Ground State Entanglement Structure. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 21:1-21:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bouland_et_al:LIPIcs.CCC.2024.21, author = {Bouland, Adam and Fefferman, Bill and Ghosh, Soumik and Metger, Tony and Vazirani, Umesh and Zhang, Chenyi and Zhou, Zixin}, title = {{Public-Key Pseudoentanglement and the Hardness of Learning Ground State Entanglement Structure}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {21:1--21:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-331-7}, ISSN = {1868-8969}, year = {2024}, volume = {300}, editor = {Santhanam, Rahul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.21}, URN = {urn:nbn:de:0030-drops-204175}, doi = {10.4230/LIPIcs.CCC.2024.21}, annote = {Keywords: Quantum computing, Quantum complexity theory, entanglement} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Scott Aaronson, Adam Bouland, Bill Fefferman, Soumik Ghosh, Umesh Vazirani, Chenyi Zhang, and Zixin Zhou. Quantum Pseudoentanglement. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 2:1-2:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{aaronson_et_al:LIPIcs.ITCS.2024.2, author = {Aaronson, Scott and Bouland, Adam and Fefferman, Bill and Ghosh, Soumik and Vazirani, Umesh and Zhang, Chenyi and Zhou, Zixin}, title = {{Quantum Pseudoentanglement}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {2:1--2:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.2}, URN = {urn:nbn:de:0030-drops-195300}, doi = {10.4230/LIPIcs.ITCS.2024.2}, annote = {Keywords: Quantum computing, Quantum complexity theory, entanglement} }
Published in: LIPIcs, Volume 266, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)
Roozbeh Bassirian, Bill Fefferman, and Kunal Marwaha. On the Power of Nonstandard Quantum Oracles. In 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 266, pp. 11:1-11:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{bassirian_et_al:LIPIcs.TQC.2023.11, author = {Bassirian, Roozbeh and Fefferman, Bill and Marwaha, Kunal}, title = {{On the Power of Nonstandard Quantum Oracles}}, booktitle = {18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)}, pages = {11:1--11:25}, 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.11}, URN = {urn:nbn:de:0030-drops-183215}, doi = {10.4230/LIPIcs.TQC.2023.11}, annote = {Keywords: quantum complexity, QCMA, expander graphs, representation theory} }
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 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Adam Bouland, Bill Fefferman, and Umesh Vazirani. Computational Pseudorandomness, the Wormhole Growth Paradox, and Constraints on the AdS/CFT Duality (Abstract). In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 63:1-63:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{bouland_et_al:LIPIcs.ITCS.2020.63, author = {Bouland, Adam and Fefferman, Bill and Vazirani, Umesh}, title = {{Computational Pseudorandomness, the Wormhole Growth Paradox, and Constraints on the AdS/CFT Duality}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {63:1--63:2}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-134-4}, ISSN = {1868-8969}, year = {2020}, volume = {151}, editor = {Vidick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.63}, URN = {urn:nbn:de:0030-drops-117486}, doi = {10.4230/LIPIcs.ITCS.2020.63}, annote = {Keywords: Quantum complexity theory, pseudorandomness, AdS/CFT correspondence} }
Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Adam Bouland, Bill Fefferman, Chinmay Nirkhe, and Umesh Vazirani. "Quantum Supremacy" and the Complexity of Random Circuit Sampling. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 15:1-15:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{bouland_et_al:LIPIcs.ITCS.2019.15, author = {Bouland, Adam and Fefferman, Bill and Nirkhe, Chinmay and Vazirani, Umesh}, title = {{"Quantum Supremacy" and the Complexity of Random Circuit Sampling}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {15:1--15:2}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-095-8}, ISSN = {1868-8969}, year = {2019}, volume = {124}, editor = {Blum, Avrim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.15}, URN = {urn:nbn:de:0030-drops-101084}, doi = {10.4230/LIPIcs.ITCS.2019.15}, annote = {Keywords: quantum supremacy, average-case hardness, verification} }
Published in: LIPIcs, Volume 111, 13th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2018)
Adam Bouland and Maris Ozols. Trading Inverses for an Irrep in the Solovay-Kitaev Theorem. In 13th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 111, pp. 6:1-6:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{bouland_et_al:LIPIcs.TQC.2018.6, author = {Bouland, Adam and Ozols, Maris}, title = {{Trading Inverses for an Irrep in the Solovay-Kitaev Theorem}}, booktitle = {13th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2018)}, pages = {6:1--6:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-080-4}, ISSN = {1868-8969}, year = {2018}, volume = {111}, editor = {Jeffery, Stacey}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2018.6}, URN = {urn:nbn:de:0030-drops-92539}, doi = {10.4230/LIPIcs.TQC.2018.6}, annote = {Keywords: Solovay-Kitaev theorem, quantum gate sets, gate set compilation} }
Published in: LIPIcs, Volume 102, 33rd Computational Complexity Conference (CCC 2018)
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)
@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} }
Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Itai Arad, Adam Bouland, Daniel Grier, Miklos Santha, Aarthi Sundaram, and Shengyu Zhang. On the Complexity of Probabilistic Trials for Hidden Satisfiability Problems. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 12:1-12:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{arad_et_al:LIPIcs.MFCS.2016.12, author = {Arad, Itai and Bouland, Adam and Grier, Daniel and Santha, Miklos and Sundaram, Aarthi and Zhang, Shengyu}, title = {{On the Complexity of Probabilistic Trials for Hidden Satisfiability Problems}}, booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)}, pages = {12:1--12:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-016-3}, ISSN = {1868-8969}, year = {2016}, volume = {58}, editor = {Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.12}, URN = {urn:nbn:de:0030-drops-64284}, doi = {10.4230/LIPIcs.MFCS.2016.12}, annote = {Keywords: computational complexity, satisfiability problems, trial and error, quantum computing, learning theory} }
Published in: LIPIcs, Volume 50, 31st Conference on Computational Complexity (CCC 2016)
Adam Bouland, Laura Mancinska, and Xue Zhang. Complexity Classification of Two-Qubit Commuting Hamiltonians. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 28:1-28:33, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{bouland_et_al:LIPIcs.CCC.2016.28, author = {Bouland, Adam and Mancinska, Laura and Zhang, Xue}, title = {{Complexity Classification of Two-Qubit Commuting Hamiltonians}}, booktitle = {31st Conference on Computational Complexity (CCC 2016)}, pages = {28:1--28:33}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-008-8}, ISSN = {1868-8969}, year = {2016}, volume = {50}, editor = {Raz, Ran}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2016.28}, URN = {urn:nbn:de:0030-drops-58469}, doi = {10.4230/LIPIcs.CCC.2016.28}, annote = {Keywords: Quantum Computing, Sampling Problems, Commuting Hamiltonians, IQP, Gate Classification Theorems} }
Feedback for Dagstuhl Publishing