Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Anurag Anshu and Tony Metger. Concentration Bounds for Quantum States and Limitations on the QAOA from Polynomial Approximations. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 5:1-5:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{anshu_et_al:LIPIcs.ITCS.2023.5, author = {Anshu, Anurag and Metger, Tony}, title = {{Concentration Bounds for Quantum States and Limitations on the QAOA from Polynomial Approximations}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {5:1--5:8}, 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.5}, URN = {urn:nbn:de:0030-drops-175085}, doi = {10.4230/LIPIcs.ITCS.2023.5}, annote = {Keywords: quantum computing, polynomial approximation, quantum optimization algorithm, QAOA, overlap gap property} }
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} }
Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Dorit Aharonov and Leo Zhou. Hamiltonian Sparsification and Gap-Simulation. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 2:1-2:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{aharonov_et_al:LIPIcs.ITCS.2019.2, author = {Aharonov, Dorit and Zhou, Leo}, title = {{Hamiltonian Sparsification and Gap-Simulation}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {2:1--2:21}, 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.2}, URN = {urn:nbn:de:0030-drops-100956}, doi = {10.4230/LIPIcs.ITCS.2019.2}, annote = {Keywords: quantum simulation, quantum Hamiltonian complexity, sparsification, quantum PCP} }
Feedback for Dagstuhl Publishing