DROPS

Document

DOI: 10.4230/LIPIcs.TQC.2023.1

Approximate Degree Lower Bounds for Oracle Identification Problems

Authors: Mark Bun and Nadezhda Voronova

Published in: LIPIcs, Volume 266, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)

Abstract

The approximate degree of a Boolean function is the minimum degree of real polynomial that approximates it pointwise. For any Boolean function, its approximate degree serves as a lower bound on its quantum query complexity, and generically lifts to a quantum communication lower bound for a related function. We introduce a framework for proving approximate degree lower bounds for certain oracle identification problems, where the goal is to recover a hidden binary string x ∈ {0, 1}ⁿ given possibly non-standard oracle access to it. Our lower bounds apply to decision versions of these problems, where the goal is to compute the parity of x. We apply our framework to the ordered search and hidden string problems, proving nearly tight approximate degree lower bounds of Ω(n/log² n) for each. These lower bounds generalize to the weakly unbounded error setting, giving a new quantum query lower bound for the hidden string problem in this regime. Our lower bounds are driven by randomized communication upper bounds for the greater-than and equality functions.

Cite as

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)

Copy BibTex To Clipboard

@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.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}
}

Search Results

Documents authored by Voronova, Nadezhda

Approximate Degree Lower Bounds for Oracle Identification Problems

Abstract

Cite as

Thanks for your feedback!

Could not send message