Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Shalev Ben-David and Srijita Kundu. Oracle Separation of QMA and QCMA with Bounded Adaptivity. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 21:1-21:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bendavid_et_al:LIPIcs.ICALP.2024.21, author = {Ben-David, Shalev and Kundu, Srijita}, title = {{Oracle Separation of QMA and QCMA with Bounded Adaptivity}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {21:1--21:18}, 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.21}, URN = {urn:nbn:de:0030-drops-201642}, doi = {10.4230/LIPIcs.ICALP.2024.21}, annote = {Keywords: Quantum computing, computational complexity} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Serge Gaspers and Jerry Zirui Li. Quantum Algorithms for Graph Coloring and Other Partitioning, Covering, and Packing Problems. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 69:1-69:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{gaspers_et_al:LIPIcs.ICALP.2024.69, author = {Gaspers, Serge and Li, Jerry Zirui}, title = {{Quantum Algorithms for Graph Coloring and Other Partitioning, Covering, and Packing Problems}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {69:1--69:20}, 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.69}, URN = {urn:nbn:de:0030-drops-202124}, doi = {10.4230/LIPIcs.ICALP.2024.69}, annote = {Keywords: Graph algorithms, quantum algorithms, graph coloring, domatic number, set cover, set partition, set packing} }
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 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Harry Buhrman, Subhasree Patro, and Florian Speelman. A Framework of Quantum Strong Exponential-Time Hypotheses. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 19:1-19:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{buhrman_et_al:LIPIcs.STACS.2021.19, author = {Buhrman, Harry and Patro, Subhasree and Speelman, Florian}, title = {{A Framework of Quantum Strong Exponential-Time Hypotheses}}, booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)}, pages = {19:1--19:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-180-1}, ISSN = {1868-8969}, year = {2021}, volume = {187}, editor = {Bl\"{a}ser, Markus and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.19}, URN = {urn:nbn:de:0030-drops-136642}, doi = {10.4230/LIPIcs.STACS.2021.19}, annote = {Keywords: complexity theory, fine-grained complexity, longest common subsequence, edit distance, quantum query complexity, strong exponential-time hypothesis} }
Published in: LIPIcs, Volume 135, 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)
Xavier Coiteux-Roy and Claude Crépeau. The RGB No-Signalling Game. In 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 135, pp. 4:1-4:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{coiteuxroy_et_al:LIPIcs.TQC.2019.4, author = {Coiteux-Roy, Xavier and Cr\'{e}peau, Claude}, title = {{The RGB No-Signalling Game}}, booktitle = {14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)}, pages = {4:1--4:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-112-2}, ISSN = {1868-8969}, year = {2019}, volume = {135}, editor = {van Dam, Wim and Man\v{c}inska, Laura}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2019.4}, URN = {urn:nbn:de:0030-drops-103965}, doi = {10.4230/LIPIcs.TQC.2019.4}, annote = {Keywords: No-Signalling, Quantum Entanglement, Non-Locality, Bell inequality, Semidefinite Programming, Non-locality Hierarchy} }
Published in: LIPIcs, Volume 73, 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)
Aleksandrs Belovs, Gilles Brassard, Peter Høyer, Marc Kaplan, Sophie Laplante, and Louis Salvail. Provably Secure Key Establishment Against Quantum Adversaries. In 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 73, pp. 3:1-3:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{belovs_et_al:LIPIcs.TQC.2017.3, author = {Belovs, Aleksandrs and Brassard, Gilles and H{\o}yer, Peter and Kaplan, Marc and Laplante, Sophie and Salvail, Louis}, title = {{Provably Secure Key Establishment Against Quantum Adversaries}}, booktitle = {12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)}, pages = {3:1--3: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.3}, URN = {urn:nbn:de:0030-drops-85816}, doi = {10.4230/LIPIcs.TQC.2017.3}, annote = {Keywords: Merkle puzzles, Key establishment schemes, Quantum cryptography, Adversary method, Average-case analysis} }
Published in: LIPIcs, Volume 27, 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)
Gilles Brassard, Luc Devroye, and Claude Gravel. Exact Classical Simulation of the GHZ Distribution. In 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 27, pp. 7-23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
@InProceedings{brassard_et_al:LIPIcs.TQC.2014.7, author = {Brassard, Gilles and Devroye, Luc and Gravel, Claude}, title = {{Exact Classical Simulation of the GHZ Distribution}}, booktitle = {9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)}, pages = {7--23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-73-6}, ISSN = {1868-8969}, year = {2014}, volume = {27}, editor = {Flammia, Steven T. and Harrow, Aram W.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2014.7}, URN = {urn:nbn:de:0030-drops-48025}, doi = {10.4230/LIPIcs.TQC.2014.7}, annote = {Keywords: Entanglement simulation, Greenberger-Horne-Zeilinger (GHZ) state, Multiparty entanglement, von Neumann's rejection algorithm, Knuth-Yao's sampling alg} }
Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)
Thomas Beth and Gilles Brassard. Quantum Algorithms (Dagstuhl Seminar 98191). Dagstuhl Seminar Report 210, pp. 1-21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1998)
@TechReport{beth_et_al:DagSemRep.210, author = {Beth, Thomas and Brassard, Gilles}, title = {{Quantum Algorithms (Dagstuhl Seminar 98191)}}, pages = {1--21}, ISSN = {1619-0203}, year = {1998}, type = {Dagstuhl Seminar Report}, number = {210}, institution = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.210}, URN = {urn:nbn:de:0030-drops-150966}, doi = {10.4230/DagSemRep.210}, }