文章基本信息
- 标题：A Tight Lower Bound For Non-Coherent Index Erasure
- 本地全文：下载
- 作者：Nathan Lindzey ; Ansis Rosmanis
- 期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
- 电子版ISSN：1868-8969
- 出版年度：2020
- 卷号：151
- 页码：1-37
- DOI：10.4230/LIPIcs.ITCS.2020.59
- 出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
- 摘要：The index erasure problem is a quantum state generation problem that asks a quantum computer to prepare a uniform superposition over the image of an injective function given by an oracle. We prove a tight Ω(â^Sn) lower bound on the quantum query complexity of the non-coherent case of the problem, where, in addition to preparing the required superposition, the algorithm is allowed to leave the ancillary memory in an arbitrary function-dependent state. This resolves an open question of Ambainis, Magnin, Roetteler, and Roland (CCC 2011), who gave a tight bound for the coherent case, the case where the ancillary memory must return to its initial state. To prove our main result, we first extend the so-called automorphism principle (Høyer et al. STOC 2007) to the general adversary method for state conversion problems (Lee et al. STOC 2011), which allows one to exploit the symmetries of these problems to lower bound their quantum query complexity. Using this method, we establish a strong connection between the quantum query complexity of non-coherent symmetric state generation problems and the well-known Krein parameters of association schemes. Krein parameters are usually hard to determine, nevertheless, we give a novel way of computing certain Krein parameters of a commutative association scheme defined over partial permutations. We believe the study of this association scheme may also be of independent interest.
- 关键词：General Adversary Method; Quantum Query Complexity; Association Schemes; Krein Parameters; Representation Theory
