In this paper, we identify a family of nonconvex continuous optimization
instances, each $d$-dimensional instance with $2^d$ local minima, to
demonstrate a quantum-classical performance separation. Specifically, we prove
that the recently proposed Quantum Hamiltonian Descent (QHD) algorithm [Leng et
al., arXiv:2303.01471] is able to solve any $d$-dimensional instance from this
family using $\widetilde{\mathcal{O}}(d^3)$ quantum queries to the function
value and $\widetilde{\mathcal{O}}(d^4)$ additional 1-qubit and 2-qubit
elementary quantum gates. On the other side, a comprehensive empirical study
suggests that representative state-of-the-art classical optimization
algorithms/solvers (including Gurobi) would require a super-polynomial time to
solve such optimization instances.

我们通过一个非凸连续优化问题家族的研究，证明了新提出的量子哈密顿下降算法可以在多项式时间内解决这个问题，并且证明了经典优化算法需要超多项式时间来解决这样的优化问题。

非凸优化中的量子 - 经典性能分离

A quantum-classical performance separation in nonconvex optimization

Identifying the best arm of a multi-armed bandit is a central problem in
bandit optimization. We study a quantum computational version of this problem
with coherent oracle access to states encoding the reward probabilities of each
arm as quantum amplitudes. Specifically, we show that we can find the best arm
with fixed confidence using
$\tilde{O}\bigl(\sqrt{\sum_{i=2}^n\Delta^{\smash{-2}}_i}\bigr)$ quantum
queries, where $\Delta_{i}$ represents the difference between the mean reward
of the best arm and the $i^\text{th}$-best arm. This algorithm, based on
variable-time amplitude amplification and estimation, gives a quadratic speedup
compared to the best possible classical result. We also prove a matching
quantum lower bound (up to poly-logarithmic factors).

文章研究了一个量子计算版本的多臂老虎机问题，使用相干的 Oracle 访问状态，用 amplitudes 编码每个臂的奖励概率。特别地，作者提出了一种基于可变时间幅度放大和估计，用  Θ(| 根号 (n)| 乘以 | 根号 ∑_i=2^n Δ^(-2)_i|) 次量子查询可以找到最佳臂的算法。这个算法与经典算法相比，速度提升了一个平方级别。作者也证明了相匹配的量子下界（多项式对数因子）

多臂赌博机的量子探索算法

Quantum exploration algorithms for multi-armed bandits

In this article we give several new results on the complexity of algorithms
that learn Boolean functions from quantum queries and quantum examples.
Hunziker et al. conjectured that for any class C of Boolean functions, the
number of quantum black-box queries which are required to exactly identify an
unknown function from C is $O(\frac{\log |C|}{\sqrt{{\hat{\gamma}}^{C}}})$,
where $\hat{\gamma}^{C}$ is a combinatorial parameter of the class C. We
essentially resolve this conjecture in the affirmative by giving a quantum
algorithm that, for any class C, identifies any unknown function from C using
$O(\frac{\log |C| \log \log |C|}{\sqrt{{\hat{\gamma}}^{C}}})$ quantum black-box
queries.
We consider a range of natural problems intermediate between the exact
learning problem (in which the learner must obtain all bits of information
about the black-box function) and the usual problem of computing a predicate
(in which the learner must obtain only one bit of information about the
black-box function). We give positive and negative results on when the quantum
and classical query complexities of these intermediate problems are
polynomially related to each other.
Finally, we improve the known lower bounds on the number of quantum examples
(as opposed to quantum black-box queries) required for $(\epsilon,\delta)$-PAC
learning any concept class of Vapnik-Chervonenkis dimension d over the domain
$\{0,1\}^n$ from $\Omega(\frac{d}{n})$ to $\Omega(\frac{1}{\epsilon}\log
\frac{1}{\delta}+d+\frac{\sqrt{d}}{\epsilon})$. This new lower bound comes
closer to matching known upper bounds for classical PAC learning.

本文介绍了通过量子查询和量子示例从学习布尔函数的算法的复杂性的新结果，其中我们探讨了中间问题的量子和经典查询复杂度与精确学习问题和谐平衡的自然问题，并提高了期望严格学习的新下界，以达到经典 PAC 学习的已知上界。