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 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 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Sevag Gharibian and Dorian Rudolph. On Polynomially Many Queries to NP or QMA Oracles. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 75:1-75:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{gharibian_et_al:LIPIcs.ITCS.2022.75, author = {Gharibian, Sevag and Rudolph, Dorian}, title = {{On Polynomially Many Queries to NP or QMA Oracles}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {75:1--75:27}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-217-4}, ISSN = {1868-8969}, year = {2022}, volume = {215}, editor = {Braverman, Mark}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.75}, URN = {urn:nbn:de:0030-drops-156717}, doi = {10.4230/LIPIcs.ITCS.2022.75}, annote = {Keywords: admissible weighting function, oracle complexity class, quantum complexity theory, Quantum Merlin Arthur (QMA), simulation of local measurement} }
Published in: LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)
Joshua Cook. Size Bounds on Low Depth Circuits for Promise Majority. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 19:1-19:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{cook:LIPIcs.FSTTCS.2020.19, author = {Cook, Joshua}, title = {{Size Bounds on Low Depth Circuits for Promise Majority}}, booktitle = {40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)}, pages = {19:1--19:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-174-0}, ISSN = {1868-8969}, year = {2020}, volume = {182}, editor = {Saxena, Nitin and Simon, Sunil}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.19}, URN = {urn:nbn:de:0030-drops-132609}, doi = {10.4230/LIPIcs.FSTTCS.2020.19}, annote = {Keywords: AC0, Approximate Counting, Approximate Majority, Promise Majority, Depth 3 Circuits, Circuit Lower Bound} }
Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
Sevag Gharibian, Stephen Piddock, and Justin Yirka. Oracle Complexity Classes and Local Measurements on Physical Hamiltonians. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 20:1-20:37, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{gharibian_et_al:LIPIcs.STACS.2020.20, author = {Gharibian, Sevag and Piddock, Stephen and Yirka, Justin}, title = {{Oracle Complexity Classes and Local Measurements on Physical Hamiltonians}}, booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)}, pages = {20:1--20:37}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-140-5}, ISSN = {1868-8969}, year = {2020}, volume = {154}, editor = {Paul, Christophe and Bl\"{a}ser, Markus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.20}, URN = {urn:nbn:de:0030-drops-118818}, doi = {10.4230/LIPIcs.STACS.2020.20}, annote = {Keywords: Quantum Merlin Arthur (QMA), simulation of local measurement, local Hamiltonian, oracle complexity class, physical Hamiltonians} }
Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Sevag Gharibian, Miklos Santha, Jamie Sikora, Aarthi Sundaram, and Justin Yirka. Quantum Generalizations of the Polynomial Hierarchy with Applications to QMA(2). In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 58:1-58:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{gharibian_et_al:LIPIcs.MFCS.2018.58, author = {Gharibian, Sevag and Santha, Miklos and Sikora, Jamie and Sundaram, Aarthi and Yirka, Justin}, title = {{Quantum Generalizations of the Polynomial Hierarchy with Applications to QMA(2)}}, booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)}, pages = {58:1--58:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-086-6}, ISSN = {1868-8969}, year = {2018}, volume = {117}, editor = {Potapov, Igor and Spirakis, Paul and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.58}, URN = {urn:nbn:de:0030-drops-96409}, doi = {10.4230/LIPIcs.MFCS.2018.58}, annote = {Keywords: Complexity Theory, Quantum Computing, Polynomial Hierarchy, Semidefinite Programming, QMA(2), Quantum Complexity} }
Published in: LIPIcs, Volume 73, 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)
Sevag Gharibian and Justin Yirka. The Complexity of Simulating Local Measurements on Quantum Systems. In 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 73, pp. 2:1-2:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{gharibian_et_al:LIPIcs.TQC.2017.2, author = {Gharibian, Sevag and Yirka, Justin}, title = {{The Complexity of Simulating Local Measurements on Quantum Systems}}, booktitle = {12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)}, pages = {2:1--2:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-034-7}, ISSN = {1868-8969}, year = {2018}, volume = {73}, editor = {Wilde, Mark M.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2017.2}, URN = {urn:nbn:de:0030-drops-85776}, doi = {10.4230/LIPIcs.TQC.2017.2}, annote = {Keywords: Complexity theory, Quantum Merlin Arthur (QMA), local Hamiltonian, local measurement, spectral gap} }