BenDavid, Shalev ;
Kothari, Robin
Quantum Distinguishing Complexity, ZeroError Algorithms, and Statistical Zero Knowledge
Abstract
We define a new query measure we call quantum distinguishing complexity, denoted QD(f) for a Boolean function f. Unlike a quantum query algorithm, which must output a state close to 0> on a 0input and a state close to 1> on a 1input, a "quantum distinguishing algorithm" can output any state, as long as the output states for any 0input and 1input are distinguishable.
Using this measure, we establish a new relationship in query complexity: For all total functions f, Q_0(f)=O~(Q(f)^5), where Q_0(f) and Q(f) denote the zeroerror and boundederror quantum query complexity of f respectively, improving on the previously known sixth power relationship.
We also define a query measure based on quantum statistical zeroknowledge proofs, QSZK(f), which is at most Q(f). We show that QD(f) in fact lower bounds QSZK(f) and not just Q(f). QD(f) also upper bounds the (positiveweights) adversary bound, which yields the following relationships for all f: Q(f) >= QSZK(f) >= QD(f) = Omega(Adv(f)). This sheds some light on why the adversary bound proves suboptimal bounds for problems like Collision and Set Equality, which have low QSZK complexity.
Lastly, we show implications for lifting theorems in communication complexity. We show that a general lifting theorem for either zeroerror quantum query complexity or for QSZK would imply a general lifting theorem for boundederror quantum query complexity.
BibTeX  Entry
@InProceedings{bendavid_et_al:LIPIcs:2019:10394,
author = {Shalev BenDavid and Robin Kothari},
title = {{Quantum Distinguishing Complexity, ZeroError Algorithms, and Statistical Zero Knowledge}},
booktitle = {14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)},
pages = {2:12:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771122},
ISSN = {18688969},
year = {2019},
volume = {135},
editor = {Wim van Dam and Laura Mancinska},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10394},
URN = {urn:nbn:de:0030drops103944},
doi = {10.4230/LIPIcs.TQC.2019.2},
annote = {Keywords: Quantum query complexity, quantum algorithms}
}
2019
Keywords: 

Quantum query complexity, quantum algorithms 
Seminar: 

14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)

Issue date: 

2019 
Date of publication: 

2019 