Approximate degree lower bounds for oracle identification problems - Nadezhda Voronova | TQC 2023
Channel: Squid: Schools for Quantum Information Development
Date: 2023-08-25

Nadezhda Voronova
Approximate degree lower bounds for oracle identification problems 
https://arxiv.org/abs/2303.03921  

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 $latex x \in \{0, 1\}^n$ 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 $latex x$.     We apply our framework to the ordered search and hidden string problems, proving nearly tight approximate degree lower bounds of $latex \Omega(n/\log^2 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.

July 28, 2023
---------

TQC 2023 | 24-28 July 2023, University of Aveiro, Portugal
http://tqc-conference.org

18th Conference on the  Theory of Quantum Computation, Communication and Cryptography.

TQC is a leading annual international conference for students and researchers working in the theoretical aspects of quantum information science. The scientific objective is to bring together the theoretical quantum information science community to present and discuss the latest advances in the field.


Organisation:
Squids - Schools for Quantum Information Development  
Universidade de Aveiro: Departamento de Matemática, CIDMA & Fábrica


Sponsors:
Phasecraft, UK
Google Quantum AI, USA
QuSoft, The Netherlands
Quantum for Life Centre, Denmark
Technology Innovation Institute, UAE
ML4Q, Germany
Dulwich Quantum