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 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)
Chris Jones, Kunal Marwaha, Juspreet Singh Sandhu, and Jonathan Shi. Random Max-CSPs Inherit Algorithmic Hardness from Spin Glasses. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 77:1-77:26, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{jones_et_al:LIPIcs.ITCS.2023.77, author = {Jones, Chris and Marwaha, Kunal and Sandhu, Juspreet Singh and Shi, Jonathan}, title = {{Random Max-CSPs Inherit Algorithmic Hardness from Spin Glasses}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {77:1--77:26}, 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.77}, URN = {urn:nbn:de:0030-drops-175804}, doi = {10.4230/LIPIcs.ITCS.2023.77}, annote = {Keywords: spin glass, overlap gap property, constraint satisfaction problem, Guerra-Toninelli interpolation} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Adrian She and Henry Yuen. Unitary Property Testing Lower Bounds by Polynomials. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 96:1-96:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{she_et_al:LIPIcs.ITCS.2023.96, author = {She, Adrian and Yuen, Henry}, title = {{Unitary Property Testing Lower Bounds by Polynomials}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {96:1--96:17}, 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.96}, URN = {urn:nbn:de:0030-drops-175995}, doi = {10.4230/LIPIcs.ITCS.2023.96}, annote = {Keywords: Quantum query complexity, polynomial method, unitary property testing, quantum proofs, invariant theory, quantum recurrence time, entanglement entropy, BQP, QMA, QMA(2)} }
Published in: LIPIcs, Volume 232, 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022)
Joao Basso, Edward Farhi, Kunal Marwaha, Benjamin Villalonga, and Leo Zhou. The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model. In 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 232, pp. 7:1-7:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{basso_et_al:LIPIcs.TQC.2022.7, author = {Basso, Joao and Farhi, Edward and Marwaha, Kunal and Villalonga, Benjamin and Zhou, Leo}, title = {{The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model}}, booktitle = {17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022)}, pages = {7:1--7:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-237-2}, ISSN = {1868-8969}, year = {2022}, volume = {232}, editor = {Le Gall, Fran\c{c}ois and Morimae, Tomoyuki}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2022.7}, URN = {urn:nbn:de:0030-drops-165144}, doi = {10.4230/LIPIcs.TQC.2022.7}, annote = {Keywords: Quantum algorithm, Max-Cut, spin glass, approximation algorithm} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Boaz Barak and Kunal Marwaha. Classical Algorithms and Quantum Limitations for Maximum Cut on High-Girth Graphs. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 14:1-14:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{barak_et_al:LIPIcs.ITCS.2022.14, author = {Barak, Boaz and Marwaha, Kunal}, title = {{Classical Algorithms and Quantum Limitations for Maximum Cut on High-Girth Graphs}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {14:1--14:21}, 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.14}, URN = {urn:nbn:de:0030-drops-156105}, doi = {10.4230/LIPIcs.ITCS.2022.14}, annote = {Keywords: approximation algorithms, QAOA, maximum cut, local distributions} }
Feedback for Dagstuhl Publishing