Approximate degree lower bounds for oracle identification problems
- URL: http://arxiv.org/abs/2303.03921v2
- Date: Mon, 22 May 2023 16:22:25 GMT
- Title: Approximate degree lower bounds for oracle identification problems
- Authors: Mark Bun, Nadezhda Voronova
- Abstract summary: We introduce a framework for proving approximate degree lower bounds for certain oracle identification problems.
Our lower bounds are driven by randomized communication upper bounds for the greater-than and equality functions.
- Score: 19.001036556917818
- License: http://creativecommons.org/licenses/by/4.0/
- 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 \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 $x$. We apply our framework to the ordered
search and hidden string problems, proving nearly tight approximate degree
lower bounds of $\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.
Related papers
- Oracle Separations for the Quantum-Classical Polynomial Hierarchy [0.0]
We study the quantum-classical hierarchy, QCPH, which is the class of languages solvable by a constant number of alternating classical quantifiers.
We give a new switching lemma for quantum algorithms which may be of independent interest.
arXiv Detail & Related papers (2024-10-24T18:12:03Z) - Quantum Query-Space Lower Bounds Using Branching Programs [0.18416014644193066]
We show the first explicit query-space lower bound for our restricted version of GQBP.
We then generalize the problem to show that the same bound holds for deciding between two strings with a constant Hamming distance.
Our results produce an alternative proof of the $Omega(sqrtn)$-lower bound on the query complexity of any non-constant symmetric Boolean function.
arXiv Detail & Related papers (2024-07-09T13:58:53Z) - Rank lower bounds on non-local quantum computation [0.0]
A non-local quantum computation (NLQC) replaces an interaction between two quantum systems with a single round of communication and shared entanglement.
We study two classes of NLQC, $f$-routing and $f$-BB84, which are of relevance to classical information theoretic cryptography and quantum position-verification.
arXiv Detail & Related papers (2024-02-28T19:00:09Z) - A one-query lower bound for unitary synthesis and breaking quantum
cryptography [7.705803563459633]
The Unitary Synthesis Problem asks whether any $n$qubit unitary $U$ can be implemented by an efficient quantum $A$ augmented with an oracle that computes an arbitrary Boolean function $f$.
In this work, we prove unitary synthesis as an efficient challenger-ad game, which enables proving lower bounds by analyzing the maximum success probability of an adversary $Af$.
arXiv Detail & Related papers (2023-10-13T05:39:42Z) - Efficient Quantum State Synthesis with One Query [0.0]
We present a time analogue quantum algorithm making a single query (in superposition) to a classical oracle.
We prove that every $n$-qubit state can be constructed to within 0.01 error by an $On/n)$-size circuit over an appropriate finite gate set.
arXiv Detail & Related papers (2023-06-02T17:49:35Z) - One-Way Ticket to Las Vegas and the Quantum Adversary [78.33558762484924]
We show that quantum Las Vegas query complexity is exactly equal to the quantum adversary bound.
This is achieved by transforming a feasible solution to the adversary inversion problem into a quantum query algorithm.
arXiv Detail & Related papers (2023-01-05T11:05:22Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits.
Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit.
We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
arXiv Detail & Related papers (2022-06-30T03:15:23Z) - Exponential Separation between Quantum and Classical Ordered Binary
Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
We study quantum Ordered Binary Decision Diagrams($OBDD$) model.
We prove lower bounds and upper bounds for OBDD with arbitrary order of input variables.
We extend hierarchy for read$k$-times Ordered Binary Decision Diagrams ($k$-OBDD$) of width.
arXiv Detail & Related papers (2022-04-22T12:37:56Z) - Resource Optimisation of Coherently Controlled Quantum Computations with
the PBS-calculus [55.2480439325792]
Coherent control of quantum computations can be used to improve some quantum protocols and algorithms.
We refine the PBS-calculus, a graphical language for coherent control inspired by quantum optics.
arXiv Detail & Related papers (2022-02-10T18:59:52Z) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation.
We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
arXiv Detail & Related papers (2022-01-31T22:19:49Z) - Zeroth-Order Algorithms for Smooth Saddle-Point Problems [117.44028458220427]
We propose several algorithms to solve saddle-point problems using zeroth-order oracles.
Our analysis shows that our convergence rate for the term is only by a $log n$ factor worse than for the first-order methods.
We also consider a mixed setup and develop 1/2th-order methods that use zeroth-order oracle for the part.
arXiv Detail & Related papers (2020-09-21T14:26:48Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.