LIPIcs, Volume 27
TQC 2014, May 21-23, 2014, Singapore
Editors: Steven T. Flammia and Aram W. Harrow
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Adam Bene Watts and John Bostanci. Quantum Event Learning and Gentle Random Measurements. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 97:1-97:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{watts_et_al:LIPIcs.ITCS.2024.97, author = {Watts, Adam Bene and Bostanci, John}, title = {{Quantum Event Learning and Gentle Random Measurements}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {97:1--97:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.97}, URN = {urn:nbn:de:0030-drops-196254}, doi = {10.4230/LIPIcs.ITCS.2024.97}, annote = {Keywords: Event learning, gentle measurments, random measurements, quantum or, threshold search, shadow tomography} }
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 234, 37th Computational Complexity Conference (CCC 2022)
Sandy Irani, Anand Natarajan, Chinmay Nirkhe, Sujit Rao, and Henry Yuen. Quantum Search-To-Decision Reductions and the State Synthesis Problem. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 5:1-5:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{irani_et_al:LIPIcs.CCC.2022.5, author = {Irani, Sandy and Natarajan, Anand and Nirkhe, Chinmay and Rao, Sujit and Yuen, Henry}, title = {{Quantum Search-To-Decision Reductions and the State Synthesis Problem}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {5:1--5:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-241-9}, ISSN = {1868-8969}, year = {2022}, volume = {234}, editor = {Lovett, Shachar}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.5}, URN = {urn:nbn:de:0030-drops-165674}, doi = {10.4230/LIPIcs.CCC.2022.5}, annote = {Keywords: Search-to-decision, state synthesis, quantum computing} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Lior Eldar. Robust Quantum Entanglement at (Nearly) Room Temperature. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 49:1-49:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{eldar:LIPIcs.ITCS.2021.49, author = {Eldar, Lior}, title = {{Robust Quantum Entanglement at (Nearly) Room Temperature}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {49:1--49:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-177-1}, ISSN = {1868-8969}, year = {2021}, volume = {185}, editor = {Lee, James R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.49}, URN = {urn:nbn:de:0030-drops-135886}, doi = {10.4230/LIPIcs.ITCS.2021.49}, annote = {Keywords: Quantum error-correcting codes, Quantum Entanglement, Quantum Locally-Testable Codes, Local Hamiltonians, quantum PCP, NLTS} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Abhijit S. Mudigonda and R. Ryan Williams. Time-Space Lower Bounds for Simulating Proof Systems with Quantum and Randomized Verifiers. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 50:1-50:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{mudigonda_et_al:LIPIcs.ITCS.2021.50, author = {Mudigonda, Abhijit S. and Williams, R. Ryan}, title = {{Time-Space Lower Bounds for Simulating Proof Systems with Quantum and Randomized Verifiers}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {50:1--50:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-177-1}, ISSN = {1868-8969}, year = {2021}, volume = {185}, editor = {Lee, James R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.50}, URN = {urn:nbn:de:0030-drops-135897}, doi = {10.4230/LIPIcs.ITCS.2021.50}, annote = {Keywords: Time-space tradeoffs, lower bounds, QMA} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Matthew Coudron and Aram W. Harrow. Universality of EPR Pairs in Entanglement-Assisted Communication Complexity, and the Communication Cost of State Conversion. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 20:1-20:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{coudron_et_al:LIPIcs.CCC.2019.20, author = {Coudron, Matthew and Harrow, Aram W.}, title = {{Universality of EPR Pairs in Entanglement-Assisted Communication Complexity, and the Communication Cost of State Conversion}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {20:1--20:25}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-116-0}, ISSN = {1868-8969}, year = {2019}, volume = {137}, editor = {Shpilka, Amir}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.20}, URN = {urn:nbn:de:0030-drops-108421}, doi = {10.4230/LIPIcs.CCC.2019.20}, annote = {Keywords: Entanglement, quantum communication complexity} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Albert Atserias and Tuomas Hakoniemi. Size-Degree Trade-Offs for Sums-of-Squares and Positivstellensatz Proofs. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 24:1-24:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{atserias_et_al:LIPIcs.CCC.2019.24, author = {Atserias, Albert and Hakoniemi, Tuomas}, title = {{Size-Degree Trade-Offs for Sums-of-Squares and Positivstellensatz Proofs}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {24:1--24:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-116-0}, ISSN = {1868-8969}, year = {2019}, volume = {137}, editor = {Shpilka, Amir}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.24}, URN = {urn:nbn:de:0030-drops-108464}, doi = {10.4230/LIPIcs.CCC.2019.24}, annote = {Keywords: Proof complexity, semialgebraic proof systems, Sums-of-Squares, Positivstellensatz, trade-offs, lower bounds, monomial size, degree} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
François Le Gall. Average-Case Quantum Advantage with Shallow Circuits. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 21:1-21:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{legall:LIPIcs.CCC.2019.21, author = {Le Gall, Fran\c{c}ois}, title = {{Average-Case Quantum Advantage with Shallow Circuits}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {21:1--21:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-116-0}, ISSN = {1868-8969}, year = {2019}, volume = {137}, editor = {Shpilka, Amir}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.21}, URN = {urn:nbn:de:0030-drops-108432}, doi = {10.4230/LIPIcs.CCC.2019.21}, annote = {Keywords: Quantum computing, circuit complexity, constant-depth circuits} }
Published in: LIPIcs, Volume 135, 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)
Alexander Cowtan, Silas Dilkes, Ross Duncan, Alexandre Krajenbrink, Will Simmons, and Seyon Sivarajah. On the Qubit Routing Problem. In 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 135, pp. 5:1-5:32, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{cowtan_et_al:LIPIcs.TQC.2019.5, author = {Cowtan, Alexander and Dilkes, Silas and Duncan, Ross and Krajenbrink, Alexandre and Simmons, Will and Sivarajah, Seyon}, title = {{On the Qubit Routing Problem}}, booktitle = {14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)}, pages = {5:1--5:32}, 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.5}, URN = {urn:nbn:de:0030-drops-103972}, doi = {10.4230/LIPIcs.TQC.2019.5}, annote = {Keywords: Quantum Computing, Qubit routing, Compilation} }
Published in: LIPIcs, Volume 135, 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)
David Gosset and John Smolin. A Compressed Classical Description of Quantum States. In 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 135, pp. 8:1-8:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{gosset_et_al:LIPIcs.TQC.2019.8, author = {Gosset, David and Smolin, John}, title = {{A Compressed Classical Description of Quantum States}}, booktitle = {14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)}, pages = {8:1--8:9}, 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.8}, URN = {urn:nbn:de:0030-drops-104005}, doi = {10.4230/LIPIcs.TQC.2019.8}, annote = {Keywords: Quantum computation, Quantum communication complexity, Classical simulation} }
Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Adam Bene Watts, Aram W. Harrow, Gurtej Kanwar, and Anand Natarajan. Algorithms, Bounds, and Strategies for Entangled XOR Games. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 10:1-10:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{benewatts_et_al:LIPIcs.ITCS.2019.10, author = {Bene Watts, Adam and Harrow, Aram W. and Kanwar, Gurtej and Natarajan, Anand}, title = {{Algorithms, Bounds, and Strategies for Entangled XOR Games}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {10:1--10:18}, 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.10}, URN = {urn:nbn:de:0030-drops-101032}, doi = {10.4230/LIPIcs.ITCS.2019.10}, annote = {Keywords: Nonlocal games, XOR Games, Pseudotelepathy games, Multipartite entanglement} }
Published in: LIPIcs, Volume 61, 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016)
Anurag Anshu, Ankit Garg, Aram W. Harrow, and Penghui Yao. Lower Bound on Expected Communication Cost of Quantum Huffman Coding. In 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 61, pp. 3:1-3:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{anshu_et_al:LIPIcs.TQC.2016.3, author = {Anshu, Anurag and Garg, Ankit and Harrow, Aram W. and Yao, Penghui}, title = {{Lower Bound on Expected Communication Cost of Quantum Huffman Coding}}, booktitle = {11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016)}, pages = {3:1--3:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-019-4}, ISSN = {1868-8969}, year = {2016}, volume = {61}, editor = {Broadbent, Anne}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2016.3}, URN = {urn:nbn:de:0030-drops-66843}, doi = {10.4230/LIPIcs.TQC.2016.3}, annote = {Keywords: Quantum information, quantum communication, expected communica- tion cost, huffman coding} }
Published in: LIPIcs, Volume 50, 31st Conference on Computational Complexity (CCC 2016)
Aram Harrow, Anand V. Natarajan, and Xiaodi Wu. Tight SoS-Degree Bounds for Approximate Nash Equilibria. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 22:1-22:25, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{harrow_et_al:LIPIcs.CCC.2016.22, author = {Harrow, Aram and Natarajan, Anand V. and Wu, Xiaodi}, title = {{Tight SoS-Degree Bounds for Approximate Nash Equilibria}}, booktitle = {31st Conference on Computational Complexity (CCC 2016)}, pages = {22:1--22:25}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-008-8}, ISSN = {1868-8969}, year = {2016}, volume = {50}, editor = {Raz, Ran}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2016.22}, URN = {urn:nbn:de:0030-drops-58565}, doi = {10.4230/LIPIcs.CCC.2016.22}, annote = {Keywords: Approximate Nash Equilibrium, Sum of Squares, LP, SDP} }
Feedback for Dagstuhl Publishing