We use a quantum annealing D-Wave 2X computer to obtain solutions to NP-hard
sparse coding problems. To reduce the dimensionality of the sparse coding
problem to fit on the quantum D-Wave 2X hardware, we passed downsampled MNIST
images through a bottleneck autoencoder. To establish a benchmark for
classification performance on this reduced dimensional data set, we used an
AlexNet-like architecture implemented in TensorFlow, obtaining a classification
score of $94.54 \pm 0.7 \%$. As a control, we showed that the same AlexNet-like
architecture produced near-state-of-the-art classification performance $(\sim
99\%)$ on the original MNIST images. To obtain a set of optimized features for
inferring sparse representations of the reduced dimensional MNIST dataset, we
imprinted on a random set of $47$ image patches followed by an off-line
unsupervised learning algorithm using stochastic gradient descent to optimize
for sparse coding. Our single-layer of sparse coding matched the stride and
patch size of the first convolutional layer of the AlexNet-like deep neural
network and contained $47$ fully-connected features, $47$ being the maximum
number of dictionary elements that could be embedded onto the D-Wave $2$X
hardware. Recent work suggests that the optimal level of sparsity corresponds
to a critical value of the trade-off parameter associated with a putative
second order phase transition, an observation supported by a free energy
analysis of D-Wave energy states. When the sparse representations inferred by
the D-Wave $2$X were passed to a linear support vector machine, we obtained a
classification score of $95.68\%$. Thus, on this problem, we find that a
single-layer of quantum inference is able to outperform a standard deep neural
network architecture.

利用量子退火 D-Wave 2X 计算机实现稀疏编码问题的最优解，通过瓶颈自编码器将 MNIST 图像降维，再使用类似 AlexNet 的 TensorFlow 结构进行分类。利用线性支持向量机对 D-Wave 2X 推断出的稀疏表示进行分类，分类准确率高达 95.68%。

使用 D-Wave 2X 上的量子推理进行图像分类

Image classification using quantum inference on the D-Wave 2X

The recent availability of the first commercial quantum computers has
provided a promising tool to tackle NP hard problems which can only be solved
heuristically with present techniques. However, it is unclear if the current
state of quantum computing already provides a quantum advantage over the
current state of the art in classical computing. This article assesses the
performance of the D-Wave 2X quantum annealer on two NP hard graph problems, in
particular clique finding and graph partitioning. For this, we provide
formulations as Qubo and Ising Hamiltonians suitable for the quantum annealer
and compare a variety of quantum solvers (Sapi, QBSolv, QSage provided by
D-Wave Sys, Inc.) to current classical algorithms (METIS, Simulated Annealing,
third-party clique finding and graph splitting heuristics) on certain test sets
of graphs. We demonstrate that for small graph instances, classical methods
still outperform the quantum annealer in terms of computing time, even though
the quality of the best solutions obtained is comparable. Nevertheless, due to
the limited problem size which can be embedded on the D-Wave 2X chip, the
aforementioned finding applies to most of problems of general nature solvable
on the quantum annealer. For instances specifically designed to fit the D-Wave
2X architecture, we observe substantial speed-ups in computing time over
classical approaches.

本文评估了 D-Wave 2X 量子退火器在 NP 难图问题（特别是团搜索和图划分）上的表现，比较了一系列量子求解器和当前的经典算法，并演示了在卡片上可以嵌入的实例中量子计算速度的大幅提升。

利用量子退火进行高效的组合优化

Efficient Combinatorial Optimization Using Quantum Annealing

Quantum annealing (QA) has been proposed as a quantum enhanced optimization
heuristic exploiting tunneling. Here, we demonstrate how finite range tunneling
can provide considerable computational advantage. For a crafted problem
designed to have tall and narrow energy barriers separating local minima, the
D-Wave 2X quantum annealer achieves significant runtime advantages relative to
Simulated Annealing (SA). For instances with 945 variables, this results in a
time-to-99%-success-probability that is $\sim 10^8$ times faster than SA
running on a single processor core. We also compared physical QA with Quantum
Monte Carlo (QMC), an algorithm that emulates quantum tunneling on classical
processors. We observe a substantial constant overhead against physical QA:
D-Wave 2X again runs up to $\sim 10^8$ times faster than an optimized
implementation of QMC on a single core. We note that there exist heuristic
classical algorithms that can solve most instances of Chimera structured
problems in a timescale comparable to the D-Wave 2X. However, we believe that
such solvers will become ineffective for the next generation of annealers
currently being designed. To investigate whether finite range tunneling will
also confer an advantage for problems of practical interest, we conduct
numerical studies on binary optimization problems that cannot yet be
represented on quantum hardware. For random instances of the number
partitioning problem, we find numerically that QMC, as well as other algorithms
designed to simulate QA, scale better than SA. We discuss the implications of
these findings for the design of next generation quantum annealers.

研究发现，D-Wave 2X 量子退火器相对于模拟退火算法和经典计算机模拟的量子隧道问题求解算法 QMC，采用短程量子隧道效应将可在某些问题中取得优异的运行时间；并探讨这些发现对下一代量子退火器设计的影响。