Source-linked AI summary
Nonnegative/binary matrix factorization with a D-Wave quantum annealer
Daniel O'Malley, Velimir V. Vesselinov, Boian S. Alexandrov, Ludmil B. Alexandrov
TL;DR
The paper addresses the limited use of D-Wave annealers in real-world computation and the open question of their performance against classical methods. It applies D-Wave 2X within an unsupervised matrix-factorization method and finds a short-time benchmark regime in which it outperforms two classical codes, while identifying practical limits on realizing that advantage.
Problem
D-Wave annealers had seen few real-world computations, and their performance benefits over classical single-core computing remained debated.
Source: §1 · p. 1Method
The paper uses alternating least squares for nonnegative/binary matrix factorization, solving each binary H column separately with the D-Wave 2X.
Source: §2 · pp. 2–3Results
Takeaways & Limitations
The NBMF algorithm can use the D-Wave 2X as a key component in unsupervised machine learning, though practical use still requires further work.
Source: §4 · p. 11To benefit from the short-time performance regime, the time to get problems into and solutions out of the D-Wave must improve.
Source: §4 · p. 10
Abstract
from arXiv · showhide
D-Wave quantum annealers represent a novel computational architecture and have attracted significant interest, but have been used for few real-world computations. Machine learning has been identified as an area where quantum annealing may be useful. Here, we show that the D-Wave 2X can be effectively used as part of an unsupervised machine learning method. This method can be used to analyze large datasets. The D-Wave only limits the number of features that can be extracted from the dataset. We apply this method to learn the features from a set of facial images.
1 Introduction
The paper explores D-Wave quantum annealing for matrix factorization and applies the resulting algorithm to facial images. It benchmarks the D-Wave against two classical approaches, reporting an advantage in a short-computation-time regime while noting that the comparison suggests a classical heuristic could do better.
1 Introduction
- The work applies a D-Wave-based matrix-factorization algorithm to learn features from facial images.The paper frames quantum annealing as one of several alternative computational architectures explored amid slowing single-core progress.Source: §1 · p. 1
- The paper benchmarks the D-Wave against two state-of-the-art classical approaches amid ongoing debate about its performance relative to classical computing.The studied matrix-factorization problem is described as real rather than synthetic, and not customized for the D-Wave.Source: §1 · p. 1
- In a benchmark on a real, non-D-Wave-tailored problem, the D-Wave outperforms two classical approaches, but a suggested classical heuristic could outperform it.The authors report an advantage over very good classical tools when only a short amount of computational time is allotted.Source: §1 · pp. 1–2
2 Methods
The method uses alternating least squares for nonnegative/binary matrix factorization, then solves each column’s binary feature assignment as a separate optimization problem. This reduces the D-Wave variable requirement to the feature count, while the benchmark compares its solutions with two classical approaches.
2 Methods
- NBMF constrains W to be nonnegative and H to binary, and alternates least-squares updates to solve for the factorization.This distinguishes NBMF from NMF, where H may take any nonnegative value.Source: §2 · p. 2
- The H update separates into independent binary least-squares problems, one for each column of H.Variables in H’s ith column affect only the ith column of WX.Source: §2 · p. 3
- The D-Wave solves only k binary variables at a time, so its restriction is on the number of features rather than dataset dimensions n and m.The full H update involves km binary variables, whereas each column-wise problem involves only k.Source: §2 · p. 3
- The benchmark compares D-Wave solutions with qbsolv and Gurobi using cumulative time-to-targets across fixed annealing budgets of 10, 100, 1,000, and 10,000 cycles.Classical solvers must match the best D-Wave solution for each instance; times exceeding 10 minutes are capped, and qbsolv reaches the cap in some cases.Source: §2 · p. 3
2.1 Programming the D-Wave
- The D-Wave’s dense quadratic interactions require embedding in its sparse hardware graph; the study limits problems to 35 binary variables.For 35 variables, each is represented by at most 19 physical qubits in the reported embedding.Source: §2.1 · p. 4
3 Results
On 2,429 facial images, NBMF learned holistic, sometimes subtle features that combine to reconstruct faces. The benchmark comparison was mixed: Gurobi beat cumulative annealing time at 10,000 anneals, while qbsolv remained slower in aggregate.
3 Results
- On 2,429 facial images, NBMF learned holistic features—including subtle, ghostly features—that could be combined to reconstruct a face, unlike NMF’s parts-based features.The displayed feature set was learned using 10,000 anneals per solve; Figure 1 shows the selected features summed to make a reconstruction.Source: §3 · pp. 4–5, Figure 1 · p. 6
- 85% sparse: NBMF’s H versus 13% for NMF; NMF’s reconstruction norm was about 46% of NBMF’s, while NBMF stores H in 1 bit versus 64-bit values.For these images, W was dense with NBMF, while NMF’s W was about 41% sparse.Source: §3 · p. 5
- About 6.4: at 10,000 anneals, Gurobi’s cumulative time-to-target was less than cumulative annealing time by this factor, while qbsolv stayed 20–50 times higher across anneal counts.Figure 3 compares cumulative solver time with cumulative annealing time; the 10,000-anneal run solved fewer QUBOs because NBMF terminated earlier.Source: §3 · p. 5, Figure 3 · p. 8
- At 10,000 anneals, qbsolv exceeded annealing time in more than 28% of problems, versus less than 1% at 10 anneals; Gurobi rarely had very long target times.Across more than 90,000 problems, Gurobi exceeded one second 21 times, while qbsolv did so 5,509 times and hit the 10-minute maximum 24 times.Source: §3 · pp. 5, 9
4 Discussion
The D-Wave 2X outperformed two state-of-the-art classical codes in a fast, good-but-not-necessarily-optimal regime on a problem not custom-tailored to its hardware. The authors emphasize that this is not quantum supremacy and identify benchmark and implementation constraints on practical performance.
4 Discussion
- In a fast, good-but-not-necessarily-optimal regime, D-Wave outperformed two state-of-the-art classical codes on a non-custom-tailored problem, but this is not quantum supremacy.The authors identify this regime using the benchmark studied here.Source: §4 · p. 9
- A short qbsolv run followed by Gurobi if the target is missed is a suggested classical heuristic that would likely outperform D-Wave.The proposal combines qbsolv’s frequent target matches with Gurobi’s ability to avoid falling too far behind D-Wave.Source: §4 · p. 9
- Different target-setting choices in the cumulative time-to-targets benchmark might cast D-Wave’s performance in a more negative light or produce different results.The authors note that letting D-Wave set targets could favor it, while reversing the target-setting roles could change the comparison.Source: §4 · p. 10
- More couplers per qubit could improve performance and allow more features, while embedding and coefficient-tuning techniques are proposed as possible algorithmic improvements.The authors describe these hardware and algorithmic improvements as expected or potential, not demonstrated results.Source: §4 · p. 10
- Practical use for large image sets depends on faster problem input and solution output; roughly 15 ms of programming time could also hinder the short-time advantage.The studied input and output used HTTPS, and the reported programming time was typically about 15 milliseconds.Source: §4 · pp. 10–11
- The authors demonstrate that NBMF can use D-Wave 2X as a key component in unsupervised machine-learning analysis, while noting that practical use still needs work.They characterize the competitive real-world result as a step toward practical quantum annealing, not its completion.Source: §4 · p. 11