License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2023.36
URN: urn:nbn:de:0030-drops-186890
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18689/
Czekanski, Michael ;
Kimmel, Shelby ;
Witter, R. Teal
Robust and Space-Efficient Dual Adversary Quantum Query Algorithms
Abstract
The general adversary dual is a powerful tool in quantum computing because it gives a query-optimal bounded-error quantum algorithm for deciding any Boolean function. Unfortunately, the algorithm uses linear qubits in the worst case, and only works if the constraints of the general adversary dual are exactly satisfied. The challenge of improving the algorithm is that it is brittle to arbitrarily small errors since it relies on a reflection over a span of vectors. We overcome this challenge and build a robust dual adversary algorithm that can handle approximately satisfied constraints. As one application of our robust algorithm, we prove that for any Boolean function with polynomially many 1-valued inputs (or in fact a slightly weaker condition) there is a query-optimal algorithm that uses logarithmic qubits. As another application, we prove that numerically derived, approximate solutions to the general adversary dual give a bounded-error quantum algorithm under certain conditions. Further, we show that these conditions empirically hold with reasonable iterations for Boolean functions with small domains. We also develop several tools that may be of independent interest, including a robust approximate spectral gap lemma, a method to compress a general adversary dual solution using the Johnson-Lindenstrauss lemma, and open-source code to find solutions to the general adversary dual.
BibTeX - Entry
@InProceedings{czekanski_et_al:LIPIcs.ESA.2023.36,
author = {Czekanski, Michael and Kimmel, Shelby and Witter, R. Teal},
title = {{Robust and Space-Efficient Dual Adversary Quantum Query Algorithms}},
booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)},
pages = {36:1--36:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-295-2},
ISSN = {1868-8969},
year = {2023},
volume = {274},
editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18689},
URN = {urn:nbn:de:0030-drops-186890},
doi = {10.4230/LIPIcs.ESA.2023.36},
annote = {Keywords: Quantum Computing, Robust Quantum Algorithms, Johnson-Lindenstrauss Lemma, Span Programs, Query Complexity, Space Complexity}
}
