Published in: LIPIcs, Volume 310, 19th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2024)
Jordi Weggemans, Marten Folkertsma, and Chris Cade. Guidable Local Hamiltonian Problems with Implications to Heuristic Ansatz State Preparation and the Quantum PCP Conjecture. In 19th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 310, pp. 10:1-10:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{weggemans_et_al:LIPIcs.TQC.2024.10, author = {Weggemans, Jordi and Folkertsma, Marten and Cade, Chris}, title = {{Guidable Local Hamiltonian Problems with Implications to Heuristic Ansatz State Preparation and the Quantum PCP Conjecture}}, booktitle = {19th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2024)}, pages = {10:1--10:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-328-7}, ISSN = {1868-8969}, year = {2024}, volume = {310}, editor = {Magniez, Fr\'{e}d\'{e}ric and Grilo, Alex Bredariol}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2024.10}, URN = {urn:nbn:de:0030-drops-206804}, doi = {10.4230/LIPIcs.TQC.2024.10}, annote = {Keywords: Quantum complexity theory, local Hamiltonian problem, quantum state ansatzes, QCMA, quantum PCP conjecture} }
Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)
Avantika Agarwal, Sevag Gharibian, Venkata Koppula, and Dorian Rudolph. Quantum Polynomial Hierarchies: Karp-Lipton, Error Reduction, and Lower Bounds. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 7:1-7:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{agarwal_et_al:LIPIcs.MFCS.2024.7, author = {Agarwal, Avantika and Gharibian, Sevag and Koppula, Venkata and Rudolph, Dorian}, title = {{Quantum Polynomial Hierarchies: Karp-Lipton, Error Reduction, and Lower Bounds}}, booktitle = {49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)}, pages = {7:1--7:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-335-5}, ISSN = {1868-8969}, year = {2024}, volume = {306}, editor = {Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.7}, URN = {urn:nbn:de:0030-drops-205632}, doi = {10.4230/LIPIcs.MFCS.2024.7}, annote = {Keywords: Quantum complexity, polynomial hierarchy} }
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 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 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Eunou Lee and Ojas Parekh. An Improved Quantum Max Cut Approximation via Maximum Matching. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 105:1-105:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{lee_et_al:LIPIcs.ICALP.2024.105, author = {Lee, Eunou and Parekh, Ojas}, title = {{An Improved Quantum Max Cut Approximation via Maximum Matching}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {105:1--105:11}, 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.105}, URN = {urn:nbn:de:0030-drops-202482}, doi = {10.4230/LIPIcs.ICALP.2024.105}, annote = {Keywords: approximation, optimization, local Hamiltonian, rounding, SDP, matching} }
Published in: LIPIcs, Volume 266, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)
Nolan J. Coble, Matthew Coudron, Jon Nelson, and Seyed Sajjad Nezhadi. Local Hamiltonians with No Low-Energy Stabilizer States. In 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 266, pp. 14:1-14:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{coble_et_al:LIPIcs.TQC.2023.14, author = {Coble, Nolan J. and Coudron, Matthew and Nelson, Jon and Nezhadi, Seyed Sajjad}, title = {{Local Hamiltonians with No Low-Energy Stabilizer States}}, booktitle = {18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)}, pages = {14:1--14:21}, 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.14}, URN = {urn:nbn:de:0030-drops-183243}, doi = {10.4230/LIPIcs.TQC.2023.14}, annote = {Keywords: Hamiltonian complexity, Stabilizer codes, Low-energy states} }
Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Lennart Bittel, Sevag Gharibian, and Martin Kliesch. The Optimal Depth of Variational Quantum Algorithms Is QCMA-Hard to Approximate. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 34:1-34:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{bittel_et_al:LIPIcs.CCC.2023.34, author = {Bittel, Lennart and Gharibian, Sevag and Kliesch, Martin}, title = {{The Optimal Depth of Variational Quantum Algorithms Is QCMA-Hard to Approximate}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {34:1--34:24}, 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.34}, URN = {urn:nbn:de:0030-drops-183045}, doi = {10.4230/LIPIcs.CCC.2023.34}, annote = {Keywords: Variational quantum algorithms (VQA), Quantum Approximate Optimization Algorithm (QAOA), circuit depth minimization, Quantum-Classical Merlin-Arthur (QCMA), hardness of approximation, hybrid quantum algorithms} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Chris Cade, Marten Folkertsma, Sevag Gharibian, Ryu Hayakawa, François Le Gall, Tomoyuki Morimae, and Jordi Weggemans. Improved Hardness Results for the Guided Local Hamiltonian Problem. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 32:1-32:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{cade_et_al:LIPIcs.ICALP.2023.32, author = {Cade, Chris and Folkertsma, Marten and Gharibian, Sevag and Hayakawa, Ryu and Le Gall, Fran\c{c}ois and Morimae, Tomoyuki and Weggemans, Jordi}, title = {{Improved Hardness Results for the Guided Local Hamiltonian Problem}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {32:1--32:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.32}, URN = {urn:nbn:de:0030-drops-180840}, doi = {10.4230/LIPIcs.ICALP.2023.32}, annote = {Keywords: Quantum computing, Quantum advantage, Quantum Chemistry, Guided Local Hamiltonian Problem} }
Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
James D. Watson, Johannes Bausch, and Sevag Gharibian. The Complexity of Translationally Invariant Problems Beyond Ground State Energies. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 54:1-54:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{watson_et_al:LIPIcs.STACS.2023.54, author = {Watson, James D. and Bausch, Johannes and Gharibian, Sevag}, title = {{The Complexity of Translationally Invariant Problems Beyond Ground State Energies}}, booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)}, pages = {54:1--54:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-266-2}, ISSN = {1868-8969}, year = {2023}, volume = {254}, editor = {Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.54}, URN = {urn:nbn:de:0030-drops-177065}, doi = {10.4230/LIPIcs.STACS.2023.54}, annote = {Keywords: Complexity, Quantum Computing, Physics, Constraint Satisfaction, Combinatorial Reconfiguration, Many-Body Physics} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Sevag Gharibian and Dorian Rudolph. Quantum Space, Ground Space Traversal, and How to Embed Multi-Prover Interactive Proofs into Unentanglement. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 53:1-53:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{gharibian_et_al:LIPIcs.ITCS.2023.53, author = {Gharibian, Sevag and Rudolph, Dorian}, title = {{Quantum Space, Ground Space Traversal, and How to Embed Multi-Prover Interactive Proofs into Unentanglement}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {53:1--53:23}, 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.53}, URN = {urn:nbn:de:0030-drops-175564}, doi = {10.4230/LIPIcs.ITCS.2023.53}, annote = {Keywords: quantum complexity theory, Quantum Merlin Arthur (QMA), QMA(2), ground state connectivity (GSCON), quantum error correction} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Abhinav Deshpande, Alexey V. Gorshkov, and Bill Fefferman. The Importance of the Spectral Gap in Estimating Ground-State Energies. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 54:1-54:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{deshpande_et_al:LIPIcs.ITCS.2022.54, author = {Deshpande, Abhinav and Gorshkov, Alexey V. and Fefferman, Bill}, title = {{The Importance of the Spectral Gap in Estimating Ground-State Energies}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {54:1--54:6}, 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.54}, URN = {urn:nbn:de:0030-drops-156501}, doi = {10.4230/LIPIcs.ITCS.2022.54}, annote = {Keywords: Local Hamiltonian problem, PSPACE, PP, QMA} }
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: Dagstuhl Reports, Volume 11, Issue 5 (2021)
Bill Fefferman, Sevag Gharibian, Norbert Schuch, and Barbara Terhal. Quantum Complexity: Theory and Application (Dagstuhl Seminar 21261). In Dagstuhl Reports, Volume 11, Issue 5, pp. 76-88, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@Article{fefferman_et_al:DagRep.11.5.76, author = {Fefferman, Bill and Gharibian, Sevag and Schuch, Norbert and Terhal, Barbara}, title = {{Quantum Complexity: Theory and Application (Dagstuhl Seminar 21261)}}, pages = {76--88}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2021}, volume = {11}, number = {5}, editor = {Fefferman, Bill and Gharibian, Sevag and Schuch, Norbert and Terhal, Barbara}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.11.5.76}, URN = {urn:nbn:de:0030-drops-155715}, doi = {10.4230/DagRep.11.5.76}, annote = {Keywords: complexity theory, many-body systems, proof and verification systems, quantum computation, quantum supremacy} }
Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
Sean Hallgren, Eunou Lee, and Ojas Parekh. An Approximation Algorithm for the MAX-2-Local Hamiltonian Problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 59:1-59:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{hallgren_et_al:LIPIcs.APPROX/RANDOM.2020.59, author = {Hallgren, Sean and Lee, Eunou and Parekh, Ojas}, title = {{An Approximation Algorithm for the MAX-2-Local Hamiltonian Problem}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)}, pages = {59:1--59:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-164-1}, ISSN = {1868-8969}, year = {2020}, volume = {176}, editor = {Byrka, Jaros{\l}aw and Meka, Raghu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.59}, URN = {urn:nbn:de:0030-drops-126629}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.59}, annote = {Keywords: approximation algorithm, quantum computing, local Hamiltonian, mean-field theory, randomized rounding} }
Published in: LIPIcs, Volume 158, 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)
Anne Broadbent, Sevag Gharibian, and Hong-Sheng Zhou. Towards Quantum One-Time Memories from Stateless Hardware. In 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 158, pp. 6:1-6:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{broadbent_et_al:LIPIcs.TQC.2020.6, author = {Broadbent, Anne and Gharibian, Sevag and Zhou, Hong-Sheng}, title = {{Towards Quantum One-Time Memories from Stateless Hardware}}, booktitle = {15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)}, pages = {6:1--6:25}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-146-7}, ISSN = {1868-8969}, year = {2020}, volume = {158}, editor = {Flammia, Steven T.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2020.6}, URN = {urn:nbn:de:0030-drops-120654}, doi = {10.4230/LIPIcs.TQC.2020.6}, annote = {Keywords: quantum cryptography, one-time memories, semi-definite programming} }
Feedback for Dagstuhl Publishing