Quantum walks (QWs) have the property that classical random walks (RWs) do
not possess -- coexistence of linear spreading and localization -- and this
property is utilized to implement various kinds of applications. This paper
proposes a quantum-walk-based algorithm for multi-armed-bandit (MAB) problems
by associating the two operations that make MAB problems difficult --
exploration and exploitation -- with these two behaviors of QWs. We show that
this new policy based on the QWs realizes high performance compared with the
corresponding RW-based one.

本文提出了一种基于量子漫步的算法来解决多臂赌博机问题，通过将探索和利用与量子漫步的两种行为联系起来，我们表明这种新的基于量子漫步的策略相对于相应的基于随机漫步的策略实现了高性能。

经典随机游走与量子游走驱动的赌博算法

Bandit Algorithm Driven by a Classical Random Walk and a Quantum Walk

We present a quantum algorithm for simulating the dynamics of Hamiltonians
that are not necessarily sparse. Our algorithm is based on the input model
where the entries of the Hamiltonian are stored in a data structure in a
quantum random access memory (qRAM) which allows for the efficient preparation
of states that encode the rows of the Hamiltonian. We use a linear combination
of quantum walks to achieve poly-logarithmic dependence on precision. The time
complexity of our algorithm, measured in terms of the circuit depth, is
$O(t\sqrt{N}\|H\|\,\mathrm{polylog}(N, t\|H\|, 1/\epsilon))$, where $t$ is the
evolution time, $N$ is the dimension of the system, and $\epsilon$ is the error
in the final state, which we call precision. Our algorithm can be directly
applied as a subroutine for unitary implementation and quantum linear systems
solvers, achieving $\widetilde{O}(\sqrt{N})$ dependence for both applications.

文中提出了一种基于量子随机存取存储器（qRAM）的算法，可以模拟不一定稀疏的哈密顿量动力学，并通过一种线性组合的量子行走实现了多项式对数精度，最后证明了该算法可以作为一个单元实现子程序，同时实现量子线性系统求解器，对于两种应用都具有 Θ(√𝑁) 的复杂度。

模拟非稀疏哈密顿量的量子算法

A quantum algorithm for simulating non-sparse Hamiltonians

We present general methods for simulating black-box Hamiltonians using
quantum walks. These techniques have two main applications: simulating sparse
Hamiltonians and implementing black-box unitary operations. In particular, we
give the best known simulation of sparse Hamiltonians with constant precision.
Our method has complexity linear in both the sparseness D (the maximum number
of nonzero elements in a column) and the evolution time t, whereas previous
methods had complexity scaling as D^4 and were superlinear in t. We also
consider the task of implementing an arbitrary unitary operation given a
black-box description of its matrix elements. Whereas standard methods for
performing an explicitly specified N x N unitary operation use O(N^2)
elementary gates, we show that a black-box unitary can be performed with
bounded error using O(N^{2/3} (log log N)^{4/3}) queries to its matrix
elements. In fact, except for pathological cases, it appears that most
unitaries can be performed with only O(sqrt{N}) queries, which is optimal.

本文提出了用量子行走模拟黑箱哈密顿量的一般方法。这些技术具有两个主要应用：模拟稀疏哈密顿量和实现黑箱酉操作。我们给出了稀疏 Hamiltonians 常数精度下最好的已知模拟方法，复杂度线性地随着稀疏矩阵的最大非零元素数 D 和演化时间 t 增长，并且我们还研究了给定黑箱描述矩阵元素的任意酉操作实现的任务。