LIPIcs, Volume 27
TQC 2014, May 21-23, 2014, Singapore
Editors: Steven T. Flammia and Aram W. Harrow
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 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} }
Published in: LIPIcs, Volume 27, 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)
Steven T. Flammia and Aram W. Harrow. LIPIcs, Volume 27, TQC'14, Complete Volume. In 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 27, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)
@Proceedings{flammia_et_al:LIPIcs.TQC.2014, title = {{LIPIcs, Volume 27, TQC'14, Complete Volume}}, booktitle = {9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)}, 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}, URN = {urn:nbn:de:0030-drops-48241}, doi = {10.4230/LIPIcs.TQC.2014}, annote = {Keywords: Data Encryption, Coding and Information Theory, Theory of Computation} }
Published in: LIPIcs, Volume 27, 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)
Steven T. Flammia and Aram W. Harrow. Front Matter, Table of Contents, Preface, Conference Organization. In 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 27, pp. i-xiv, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)
@InProceedings{flammia_et_al:LIPIcs.TQC.2014.i, author = {Flammia, Steven T. and Harrow, Aram W.}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)}, pages = {i--xiv}, 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.i}, URN = {urn:nbn:de:0030-drops-48197}, doi = {10.4230/LIPIcs.TQC.2014.i}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Published in: LIPIcs, Volume 27, 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)
Jean-Daniel Bancal and Valerio Scarani. More Randomness From Noisy Sources. In 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 27, pp. 1-6, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)
@InProceedings{bancal_et_al:LIPIcs.TQC.2014.1, author = {Bancal, Jean-Daniel and Scarani, Valerio}, title = {{More Randomness From Noisy Sources}}, booktitle = {9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)}, pages = {1--6}, 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.1}, URN = {urn:nbn:de:0030-drops-48015}, doi = {10.4230/LIPIcs.TQC.2014.1}, annote = {Keywords: Randomness, Bell inequalities, Trusted provider assumption} }
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} }
Feedback for Dagstuhl Publishing