Tight Quantum Lower Bound for Approximate Counting with Quantum States
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2020
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929336982962176 |
|---|---|
| author | Belovs, Aleksandrs Rosmanis, Ansis |
| author_facet | Belovs, Aleksandrs Rosmanis, Ansis |
| contents | We prove tight lower bounds for the following variant of the counting problem considered by Aaronson, Kothari, Kretschmer, and Thaler (2020). The task is to distinguish whether an input set $x\subseteq [n]$ has size either $k$ or $k'=(1+\varepsilon)k$. We assume the algorithm has access to
* the membership oracle, which, for each $i\in [n]$, can answer whether $i\in x$, or not; and \item the uniform superposition $|ψ_x\rangle = \sum_{i\in x} |i\rangle/\sqrt{|x|}$ over the elements of $x$. Moreover, we consider three different ways how the algorithm can access this state:
- the algorithm can have copies of the state $|ψ_x\rangle$;
- the algorithm can execute the reflecting oracle which reflects about the state $|ψ_x\rangle$;
- the algorithm can execute the state-generating oracle (or its inverse) which performs the transformation $|0\rangle\mapsto|ψ_x\rangle$.
Without the second type of resources (the ones related to $|ψ_x\rangle$), the problem is well-understood. The study of the problem with the second type of resources was recently initiated by Aaronson et al. We completely resolve the problem for all values of $1/k \le \varepsilon\le 1$, giving tight trade-offs between all types of resources available to the algorithm. We also demonstrate that our lower bounds are tight. Thus, we close the main open problems from Aaronson et al.
The lower bounds are proven using variants of the adversary bound from Belovs (2015) and employing representation theory of the symmetric group applied to the $S_n$-modules $\mathbb{C}^{\binom{[n]}k}$ and $\mathbb{C}^{\binom{[n]}k}\otimes \mathbb{C}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2002_06879 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Tight Quantum Lower Bound for Approximate Counting with Quantum States Belovs, Aleksandrs Rosmanis, Ansis Quantum Physics We prove tight lower bounds for the following variant of the counting problem considered by Aaronson, Kothari, Kretschmer, and Thaler (2020). The task is to distinguish whether an input set $x\subseteq [n]$ has size either $k$ or $k'=(1+\varepsilon)k$. We assume the algorithm has access to * the membership oracle, which, for each $i\in [n]$, can answer whether $i\in x$, or not; and \item the uniform superposition $|ψ_x\rangle = \sum_{i\in x} |i\rangle/\sqrt{|x|}$ over the elements of $x$. Moreover, we consider three different ways how the algorithm can access this state: - the algorithm can have copies of the state $|ψ_x\rangle$; - the algorithm can execute the reflecting oracle which reflects about the state $|ψ_x\rangle$; - the algorithm can execute the state-generating oracle (or its inverse) which performs the transformation $|0\rangle\mapsto|ψ_x\rangle$. Without the second type of resources (the ones related to $|ψ_x\rangle$), the problem is well-understood. The study of the problem with the second type of resources was recently initiated by Aaronson et al. We completely resolve the problem for all values of $1/k \le \varepsilon\le 1$, giving tight trade-offs between all types of resources available to the algorithm. We also demonstrate that our lower bounds are tight. Thus, we close the main open problems from Aaronson et al. The lower bounds are proven using variants of the adversary bound from Belovs (2015) and employing representation theory of the symmetric group applied to the $S_n$-modules $\mathbb{C}^{\binom{[n]}k}$ and $\mathbb{C}^{\binom{[n]}k}\otimes \mathbb{C}$. |
| title | Tight Quantum Lower Bound for Approximate Counting with Quantum States |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2002.06879 |