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} }
Published in: LIPIcs, Volume 158, 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)
Anurag Anshu, David Gosset, and Karen Morenz. Beyond Product State Approximations for a Quantum Analogue of Max Cut. In 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 158, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{anshu_et_al:LIPIcs.TQC.2020.7, author = {Anshu, Anurag and Gosset, David and Morenz, Karen}, title = {{Beyond Product State Approximations for a Quantum Analogue of Max Cut}}, booktitle = {15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)}, pages = {7:1--7:15}, 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.7}, URN = {urn:nbn:de:0030-drops-120660}, doi = {10.4230/LIPIcs.TQC.2020.7}, annote = {Keywords: Approximation algorithms, Quantum many-body systems} }
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 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Sevag Gharibian and Ojas Parekh. Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 31:1-31:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{gharibian_et_al:LIPIcs.APPROX-RANDOM.2019.31, author = {Gharibian, Sevag and Parekh, Ojas}, title = {{Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {31:1--31:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-125-2}, ISSN = {1868-8969}, year = {2019}, volume = {145}, editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.31}, URN = {urn:nbn:de:0030-drops-112463}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.31}, annote = {Keywords: Approximation algorithm, Max-Cut, local Hamiltonian, QMA-hard, Heisenberg model, product state} }
Feedback for Dagstuhl Publishing