Improving solutions by embedding larger subproblems in a D-Wave quantum annealer
Open accessThe DOI matches its Crossref record; 11 of the 11 references it cites were found in a registry or an index.
Abstract
Quantum annealing is a heuristic algorithm that solves combinatorial optimization problems, and D-Wave Systems Inc. has developed hardware implementation of this algorithm. However, in general, we cannot embed all the logical variables of a large-scale problem, since the number of available qubits is limited. In order to handle a large problem, has been proposed as a method for partitioning the original large problem into subproblems that are embeddable in the D-Wave quantum annealer, and it then iteratively optimizes the subproblems using the quantum annealer. Multiple logical variables in the subproblem are simultaneously updated in this iterative solver, and using this approach we expect to obtain better solutions than can be obtained by conventional local search algorithms. Although embedding of large subproblems is essential for improving the accuracy of solutions in this scheme, the size of the subproblems are small in since the subproblems are basically embedded by using an embedding of a complete graph even for sparse problem graphs. This means that the resource of the D-Wave quantum annealer is not exploited efficiently. In this paper, we propose a fast algorithm for embedding larger subproblems, and we show that better solutions are obtained efficiently by embedding larger subproblems.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Ising formulations of many NP problems
Lucas, A. (2014) · Frontiers in Physics · doi:10.3389/fphy.2014.00005 · Cited by 2,512
Quantum annealing in the transverse Ising model
Kadowaki, T., & Nishimori, H. (1998) · Physical Review E · doi:10.1103/physreve.58.5355 · Cited by 2,339 · cited 2×
“main closed to the instantaneous groundstate of the time-dependentHamiltonian if the system changes sufficiently slowly and if the adiabatic condition13, 1 [ε1(t)−ε0(t)] 2 h1(t)| dHˆ(t) dt |0(t)i ≪ 1, (3) Figure 1. A Chimera graph for (M,N,L)=(3,3,4). The nine complete bipartite graphs K4,4 are arrangedin a grid patter…”
BackgroundQuantum annealing with manufactured spins
Johnson, M. W., Amin, M. H. S., Gildert, S., Lanting, T., Hamze, F., Dickson, N., Harris, R., Berkley, A. J., Johansson, J., Bunyk, P., et al. (2011) · Nature · doi:10.1038/nature10012 · Cited by 1,891
Defining and detecting quantum speedup
Rønnow, T. F., Wang, Z., Job, J., Boixo, S., Isakov, S. V., Wecker, D., Martinis, J. M., Lidar, D. A., & Troyer, M. (2014) · Science · doi:10.1126/science.1252319 · Cited by 601
Amin, M. H., Andriyash, E., Rolfe, J., Kulchytskyy, B., & Melko, R. (2018) · Physical Review X · doi:10.1103/physrevx.8.021050 · Cited by 520
What is the Computational Value of Finite-Range Tunneling?
Denchev, V. S., Boixo, S., Isakov, S. V., Ding, N., Babbush, R., Smelyanskiy, V., Martinis, J., & Neven, H. (2016) · Physical Review X · doi:10.1103/physrevx.6.031015 · Cited by 399
Mathematical foundation of quantum annealing
Morita, S., & Nishimori, H. (2008) · Journal of Mathematical Physics · doi:10.1063/1.2995837 · Cited by 381 · cited 1×
“ments are forbidden. The computational time Tprop for the proposed algorithm and the number Nbreadth of the shortest paths searched by the breadth-first search are given by Tprop ∼O(NbreadthTbreadth), (13) Nbreadth ∼|Ep|. (14) The computationaltime Tbreadth for the breadth-firstsearch is given by Tbreadth ∼O |eq| , (15)…”
MethodBenedetti, M., Realpe-Gómez, J., Biswas, R., & Perdomo-Ortiz, A. (2016) · Physical Review A · doi:10.1103/physreva.94.022308 · Cited by 215
Application of Quantum Annealing to Training of Deep Neural Networks
Adachi, S. H., & Henderson, M. P. (2015) · arXiv · doi:10.48550/arxiv.1510.06356 · Cited by 176
Nonnegative/Binary matrix factorization with a D-Wave quantum annealer
O’Malley, D., Vesselinov, V. V., Alexandrov, B. S., & Alexandrov, L. B. (2018) · PLOS ONE · doi:10.1371/journal.pone.0206653 · Cited by 140 · cited 1×
“…based on superconducting flux qubits 8 has been developed by D-Wave Systems Inc. Experimental studies using the D-Wave quantum annealer have been performed to compare the performance of QA and SA 6,9 and to demonstrate the applicability of the D-Wave quantum annealer to practical problems 10–12 .”
Method
Cited by
Quantum annealing for industry applications: introduction and review
Yarkoni, S., Raponi, E., Bäck, T., & Schmitt, S. (2022) · Reports on Progress in Physics · doi:10.1088/1361-6633/ac8c54 · Cited by 341
Ajagekar, A., Humble, T., & You, F. (2020) · Computers & Chemical Engineering · doi:10.1016/j.compchemeng.2019.106630 · Cited by 191
“Since the Chimera lattice is not fully connected, mapping of variables to physical qubits uses the process of minor-embedding and is crucial to problem solving [30-33].”
BackgroundApplication of Quantum Annealing to Nurse Scheduling Problem
Ikeda, K., Nakamura, Y., & Humble, T. S. (2019) · Scientific Reports · doi:10.1038/s41598-019-49172-3 · Cited by 139
Reinforcement Quantum Annealing: A Hybrid Quantum Learning Automata
Ayanzadeh, R., Halem, M., & Finin, T. (2020) · Scientific Reports · doi:10.1038/s41598-020-64078-1 · Cited by 57
Quantum Shuttle: traffic navigation with Quantum computing
Yarkoni, S., Neukart, F., Tagle, E. M. G., Magiera, N., Mehta, B., Hire, K., Narkhede, S., & Hofmann, M. (2020) · Proceedings of the 1st ACM SIGSOFT International Workshop on Architectures and Paradigms for Engineering Quantum Software · doi:10.1145/3412451.3428500 · Cited by 50
Metadata
- Authors
- Okada, S., Ohzeki, M., Terabe, M., & Taguchi, S.
- Venue
- Scientific Reports
- Published
- 2019-02-14
- Volume
- 9
- Issue
- 1
- Pages
- 2098-2098
- ISSN
- 2045-2322 (ISSN-L)
- OpenAlex
- W2907782024
- Cited by
- 92
- References
- 11
- FWCI
- 5.76
- Type
- journal article
- Language
- en
- Open access
- gold
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Improving solutions by embedding larger subproblems in a D-Wave quantum annealer. https://app.cochat.ai/papers/10.1038/s41598-018-38388-4
- The paper
- Okada, S., Ohzeki, M., Terabe, M., & Taguchi, S. (2019). Improving solutions by embedding larger subproblems in a D-Wave quantum annealer. Scientific Reports. https://doi.org/10.1038/s41598-018-38388-4
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.