Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Sabee Grewal and Justin Yirka. The Entangled Quantum Polynomial Hierarchy Collapses. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 6:1-6:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{grewal_et_al:LIPIcs.CCC.2024.6, author = {Grewal, Sabee and Yirka, Justin}, title = {{The Entangled Quantum Polynomial Hierarchy Collapses}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {6:1--6: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.6}, URN = {urn:nbn:de:0030-drops-204028}, doi = {10.4230/LIPIcs.CCC.2024.6}, annote = {Keywords: Polynomial hierarchy, Entangled proofs, Correlated proofs, Minimax} }
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 300, 39th Computational Complexity Conference (CCC 2024)
Fernando Granha Jeronimo and Pei Wu. Dimension Independent Disentanglers from Unentanglement and Applications. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 26:1-26:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{jeronimo_et_al:LIPIcs.CCC.2024.26, author = {Jeronimo, Fernando Granha and Wu, Pei}, title = {{Dimension Independent Disentanglers from Unentanglement and Applications}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {26:1--26:28}, 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.26}, URN = {urn:nbn:de:0030-drops-204228}, doi = {10.4230/LIPIcs.CCC.2024.26}, annote = {Keywords: QMA(2), disentangler, quantum proofs} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Elie Abboud and Noga Ron-Zewi. Finer-Grained Reductions in Fine-Grained Hardness of Approximation. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 7:1-7:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{abboud_et_al:LIPIcs.ICALP.2024.7, author = {Abboud, Elie and Ron-Zewi, Noga}, title = {{Finer-Grained Reductions in Fine-Grained Hardness of Approximation}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {7:1--7:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.7}, URN = {urn:nbn:de:0030-drops-201507}, doi = {10.4230/LIPIcs.ICALP.2024.7}, annote = {Keywords: Fine-grained complexity, conditional lower bound, fine-grained reduction, Approximation algorithms, Analysis of algorithms, Computational geometry, Computational and structural complexity theory} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Srinivasan Arunachalam, Arkopal Dutt, Francisco Escudero Gutiérrez, and Carlos Palazuelos. Learning Low-Degree Quantum Objects. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 13:1-13:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{arunachalam_et_al:LIPIcs.ICALP.2024.13, author = {Arunachalam, Srinivasan and Dutt, Arkopal and Escudero Guti\'{e}rrez, Francisco and Palazuelos, Carlos}, title = {{Learning Low-Degree Quantum Objects}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {13:1--13:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.13}, URN = {urn:nbn:de:0030-drops-201563}, doi = {10.4230/LIPIcs.ICALP.2024.13}, annote = {Keywords: Tomography} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Shalev Ben-David and Srijita Kundu. Oracle Separation of QMA and QCMA with Bounded Adaptivity. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 21:1-21:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bendavid_et_al:LIPIcs.ICALP.2024.21, author = {Ben-David, Shalev and Kundu, Srijita}, title = {{Oracle Separation of QMA and QCMA with Bounded Adaptivity}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {21:1--21:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.21}, URN = {urn:nbn:de:0030-drops-201642}, doi = {10.4230/LIPIcs.ICALP.2024.21}, annote = {Keywords: Quantum computing, computational complexity} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Sevag Gharibian and Jonas Kamminga. BQP, Meet NP: Search-To-Decision Reductions and Approximate Counting. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 70:1-70:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{gharibian_et_al:LIPIcs.ICALP.2024.70, author = {Gharibian, Sevag and Kamminga, Jonas}, title = {{BQP, Meet NP: Search-To-Decision Reductions and Approximate Counting}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {70:1--70:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.70}, URN = {urn:nbn:de:0030-drops-202134}, doi = {10.4230/LIPIcs.ICALP.2024.70}, annote = {Keywords: Approximate Counting, Search to Decision Reduction, BQP, NP, Oracle Complexity Class} }
Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)
Ziyi Guan, Yunqi Huang, Penghui Yao, and Zekun Ye. Quantum and Classical Communication Complexity of Permutation-Invariant Functions. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 39:1-39:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{guan_et_al:LIPIcs.STACS.2024.39, author = {Guan, Ziyi and Huang, Yunqi and Yao, Penghui and Ye, Zekun}, title = {{Quantum and Classical Communication Complexity of Permutation-Invariant Functions}}, booktitle = {41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)}, pages = {39:1--39:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-311-9}, ISSN = {1868-8969}, year = {2024}, volume = {289}, editor = {Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.39}, URN = {urn:nbn:de:0030-drops-197498}, doi = {10.4230/LIPIcs.STACS.2024.39}, annote = {Keywords: Communication complexity, Permutation-invariant functions, Log-rank Conjecture, Quantum advantages} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Scott Aaronson, Harry Buhrman, and William Kretschmer. A Qubit, a Coin, and an Advice String Walk into a Relational Problem. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 1:1-1:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{aaronson_et_al:LIPIcs.ITCS.2024.1, author = {Aaronson, Scott and Buhrman, Harry and Kretschmer, William}, title = {{A Qubit, a Coin, and an Advice String Walk into a Relational Problem}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {1:1--1:24}, 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.1}, URN = {urn:nbn:de:0030-drops-195290}, doi = {10.4230/LIPIcs.ITCS.2024.1}, annote = {Keywords: Relational problems, quantum advice, randomized advice, FBQP, FBPP} }
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 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Jiawei Li. Total NP Search Problems with Abundant Solutions. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 75:1-75:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{li:LIPIcs.ITCS.2024.75, author = {Li, Jiawei}, title = {{Total NP Search Problems with Abundant Solutions}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {75:1--75:23}, 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.75}, URN = {urn:nbn:de:0030-drops-196031}, doi = {10.4230/LIPIcs.ITCS.2024.75}, annote = {Keywords: TFNP, Pigeonhole Principle} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Adam Bene Watts and John Bostanci. Quantum Event Learning and Gentle Random Measurements. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 97:1-97:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{watts_et_al:LIPIcs.ITCS.2024.97, author = {Watts, Adam Bene and Bostanci, John}, title = {{Quantum Event Learning and Gentle Random Measurements}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {97:1--97:22}, 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.97}, URN = {urn:nbn:de:0030-drops-196254}, doi = {10.4230/LIPIcs.ITCS.2024.97}, annote = {Keywords: Event learning, gentle measurments, random measurements, quantum or, threshold search, shadow tomography} }
Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)
Supartha Podder, Penghui Yao, and Zekun Ye. On the Fine-Grained Query Complexity of Symmetric Functions. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 55:1-55:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{podder_et_al:LIPIcs.ISAAC.2023.55, author = {Podder, Supartha and Yao, Penghui and Ye, Zekun}, title = {{On the Fine-Grained Query Complexity of Symmetric Functions}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {55:1--55:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-289-1}, ISSN = {1868-8969}, year = {2023}, volume = {283}, editor = {Iwata, Satoru and Kakimura, Naonori}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.55}, URN = {urn:nbn:de:0030-drops-193570}, doi = {10.4230/LIPIcs.ISAAC.2023.55}, annote = {Keywords: Query complexity, Symmetric functions, Quantum advantages} }
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)
Andris Ambainis and Aleksandrs Belovs. An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 24:1-24:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{ambainis_et_al:LIPIcs.CCC.2023.24, author = {Ambainis, Andris and Belovs, Aleksandrs}, title = {{An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {24:1--24:13}, 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.24}, URN = {urn:nbn:de:0030-drops-182943}, doi = {10.4230/LIPIcs.CCC.2023.24}, annote = {Keywords: Polynomials, Quantum Adversary Bound, Separations in Query Complexity} }