LIPIcs, Volume 266
TQC 2023, July 24-28, 2023, Aveiro, Portugal
Editors: Omar Fawzi and Michael Walter
Published in: LIPIcs, Volume 266, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)
18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 266, pp. 1-314, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@Proceedings{fawzi_et_al:LIPIcs.TQC.2023, title = {{LIPIcs, Volume 266, TQC 2023, Complete Volume}}, booktitle = {18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)}, pages = {1--314}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2023}, URN = {urn:nbn:de:0030-drops-183099}, doi = {10.4230/LIPIcs.TQC.2023}, annote = {Keywords: LIPIcs, Volume 266, TQC 2023, Complete Volume} }
Published in: LIPIcs, Volume 266, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)
18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 266, pp. 0:i-0:xii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{fawzi_et_al:LIPIcs.TQC.2023.0, author = {Fawzi, Omar and Walter, Michael}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)}, pages = {0:i--0:xii}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2023.0}, URN = {urn:nbn:de:0030-drops-183102}, doi = {10.4230/LIPIcs.TQC.2023.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Published in: LIPIcs, Volume 266, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)
Mark Bun and Nadezhda Voronova. Approximate Degree Lower Bounds for Oracle Identification Problems. In 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 266, pp. 1:1-1:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{bun_et_al:LIPIcs.TQC.2023.1, author = {Bun, Mark and Voronova, Nadezhda}, title = {{Approximate Degree Lower Bounds for Oracle Identification Problems}}, booktitle = {18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)}, pages = {1:1--1:24}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2023.1}, URN = {urn:nbn:de:0030-drops-183113}, doi = {10.4230/LIPIcs.TQC.2023.1}, annote = {Keywords: Approximate degree, quantum query complexity, communication complexity, ordered search, polynomial approximations, polynomial method} }
Published in: LIPIcs, Volume 266, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)
Marcel Dall'Agnol and Nicholas Spooner. On the Necessity of Collapsing for Post-Quantum and Quantum Commitments. In 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 266, pp. 2:1-2:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{dallagnol_et_al:LIPIcs.TQC.2023.2, author = {Dall'Agnol, Marcel and Spooner, Nicholas}, title = {{On the Necessity of Collapsing for Post-Quantum and Quantum Commitments}}, booktitle = {18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)}, pages = {2:1--2:23}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2023.2}, URN = {urn:nbn:de:0030-drops-183127}, doi = {10.4230/LIPIcs.TQC.2023.2}, annote = {Keywords: Quantum cryptography, Commitment schemes, Hash functions, Quantum rewinding} }
Published in: LIPIcs, Volume 266, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)
Srinivasan Arunachalam, Sergey Bravyi, Arkopal Dutt, and Theodore J. Yoder. Optimal Algorithms for Learning Quantum Phase States. In 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 266, pp. 3:1-3:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{arunachalam_et_al:LIPIcs.TQC.2023.3, author = {Arunachalam, Srinivasan and Bravyi, Sergey and Dutt, Arkopal and Yoder, Theodore J.}, title = {{Optimal Algorithms for Learning Quantum Phase States}}, booktitle = {18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)}, pages = {3:1--3:24}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2023.3}, URN = {urn:nbn:de:0030-drops-183139}, doi = {10.4230/LIPIcs.TQC.2023.3}, annote = {Keywords: Tomography, binary phase states, generalized phase states, IQP circuits} }
Published in: LIPIcs, Volume 266, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)
Alper Çakan, Vipul Goyal, Chen-Da Liu-Zhang, and João Ribeiro. Computational Quantum Secret Sharing. In 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 266, pp. 4:1-4:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{cakan_et_al:LIPIcs.TQC.2023.4, author = {\c{C}akan, Alper and Goyal, Vipul and Liu-Zhang, Chen-Da and Ribeiro, Jo\~{a}o}, title = {{Computational Quantum Secret Sharing}}, booktitle = {18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)}, pages = {4:1--4:26}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2023.4}, URN = {urn:nbn:de:0030-drops-183144}, doi = {10.4230/LIPIcs.TQC.2023.4}, annote = {Keywords: Quantum secret sharing, quantum cryptography} }
Published in: LIPIcs, Volume 266, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)
Stacey Jeffery, Shelby Kimmel, and Alvaro Piedrafita. Quantum Algorithm for Path-Edge Sampling. In 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 266, pp. 5:1-5:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{jeffery_et_al:LIPIcs.TQC.2023.5, author = {Jeffery, Stacey and Kimmel, Shelby and Piedrafita, Alvaro}, title = {{Quantum Algorithm for Path-Edge Sampling}}, booktitle = {18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)}, pages = {5:1--5:28}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2023.5}, URN = {urn:nbn:de:0030-drops-183151}, doi = {10.4230/LIPIcs.TQC.2023.5}, annote = {Keywords: Algorithm design and analysis, Query complexity, Graph algorithms, Span program algorithm, Path finding, Path detection} }
Published in: LIPIcs, Volume 266, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)
Daniel Hothem, Ojas Parekh, and Kevin Thompson. Improved Approximations for Extremal Eigenvalues of Sparse Hamiltonians. In 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 266, pp. 6:1-6:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{hothem_et_al:LIPIcs.TQC.2023.6, author = {Hothem, Daniel and Parekh, Ojas and Thompson, Kevin}, title = {{Improved Approximations for Extremal Eigenvalues of Sparse Hamiltonians}}, booktitle = {18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)}, pages = {6:1--6:10}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2023.6}, URN = {urn:nbn:de:0030-drops-183163}, doi = {10.4230/LIPIcs.TQC.2023.6}, annote = {Keywords: Approximation algorithms, Extremal eigenvalues, Sparse Hamiltonians, Fermionic Hamiltonians, Qubit Hamiltonians} }
Published in: LIPIcs, Volume 266, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)
Andris Ambainis, Martins Kokainis, and Jevgēnijs Vihrovs. Improved Algorithm and Lower Bound for Variable Time Quantum Search. In 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 266, pp. 7:1-7:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{ambainis_et_al:LIPIcs.TQC.2023.7, author = {Ambainis, Andris and Kokainis, Martins and Vihrovs, Jevg\={e}nijs}, title = {{Improved Algorithm and Lower Bound for Variable Time Quantum Search}}, booktitle = {18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)}, pages = {7:1--7:18}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2023.7}, URN = {urn:nbn:de:0030-drops-183177}, doi = {10.4230/LIPIcs.TQC.2023.7}, annote = {Keywords: quantum search, amplitude amplification} }
Published in: LIPIcs, Volume 266, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)
Nishant Rodrigues and Brad Lackey. Fully Device-Independent Quantum Key Distribution Using Synchronous Correlations. In 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 266, pp. 8:1-8:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{rodrigues_et_al:LIPIcs.TQC.2023.8, author = {Rodrigues, Nishant and Lackey, Brad}, title = {{Fully Device-Independent Quantum Key Distribution Using Synchronous Correlations}}, booktitle = {18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)}, pages = {8:1--8:22}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2023.8}, URN = {urn:nbn:de:0030-drops-183185}, doi = {10.4230/LIPIcs.TQC.2023.8}, annote = {Keywords: quantum cryptography, device independence, key distribution, security proofs, randomness} }
Published in: LIPIcs, Volume 266, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)
Ryo Hiromasa, Akihiro Mizutani, Yuki Takeuchi, and Seiichiro Tani. Rewindable Quantum Computation and Its Equivalence to Cloning and Adaptive Postselection. In 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 266, pp. 9:1-9:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{hiromasa_et_al:LIPIcs.TQC.2023.9, author = {Hiromasa, Ryo and Mizutani, Akihiro and Takeuchi, Yuki and Tani, Seiichiro}, title = {{Rewindable Quantum Computation and Its Equivalence to Cloning and Adaptive Postselection}}, booktitle = {18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)}, pages = {9:1--9:23}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2023.9}, URN = {urn:nbn:de:0030-drops-183193}, doi = {10.4230/LIPIcs.TQC.2023.9}, annote = {Keywords: Quantum computing, Postselection, Lattice problems} }
Published in: LIPIcs, Volume 266, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)
William Kretschmer. Quantum Mass Production Theorems. In 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 266, pp. 10:1-10:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{kretschmer:LIPIcs.TQC.2023.10, author = {Kretschmer, William}, title = {{Quantum Mass Production Theorems}}, booktitle = {18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)}, pages = {10:1--10:11}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2023.10}, URN = {urn:nbn:de:0030-drops-183206}, doi = {10.4230/LIPIcs.TQC.2023.10}, annote = {Keywords: mass production, quantum circuit synthesis, quantum circuit complexity} }
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-dev.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 266, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)
Scott Aaronson and Sabee Grewal. Efficient Tomography of Non-Interacting-Fermion States. In 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 266, pp. 12:1-12:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{aaronson_et_al:LIPIcs.TQC.2023.12, author = {Aaronson, Scott and Grewal, Sabee}, title = {{Efficient Tomography of Non-Interacting-Fermion States}}, booktitle = {18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)}, pages = {12:1--12:18}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2023.12}, URN = {urn:nbn:de:0030-drops-183222}, doi = {10.4230/LIPIcs.TQC.2023.12}, annote = {Keywords: free-fermions, Gaussian fermions, non-interacting fermions, quantum state tomography, efficient tomography} }
Feedback for Dagstuhl Publishing