CoChat

Breaking limitation of quantum annealer in solving optimization problems under constraints

Open access
Ohzeki, Masayuki · 2020 · Scientific Reports
Cited by 64

The DOI matches its Crossref record; 7 of the 7 references it cites were found in a registry or an index.

Abstract

Quantum annealing is a generic solver for optimization problems that uses fictitious quantum fluctuation. The most groundbreaking progress in the research field of quantum annealing is its hardware implementation, i.e., the so-called quantum annealer, using artificial spins. However, the connectivity between the artificial spins is sparse and limited on a special network known as the chimera graph. Several embedding techniques have been proposed, but the number of logical spins, which represents the optimization problems to be solved, is drastically reduced. In particular, an optimization problem including fully or even partly connected spins suffers from low embeddable size on the chimera graph. In the present study, we propose an alternative approach to solve a large-scale optimization problem on the chimera graph via a well-known method in statistical mechanics called the Hubbard-Stratonovich transformation or its variants. The proposed method can be used to deal with a fully connected Ising model without embedding on the chimera graph and leads to nontrivial results of the optimization problem. We tested the proposed method with a number of partition problems involving solving linear equations and the traffic flow optimization problem in Sendai and Kyoto cities in Japan.

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.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1038/s41598-020-60022-5

Cites

7 of 7 references verified0 citation errors · 0 not checkable

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.

A few free checks a day · papers already verified open instantly · results are public

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

Show all 7 references

Research works printed but not linked: 49

  1. Kirkpatrick, S., Gelatt, C. D. & Vecchi, M. P. Optimization by simulated annealing. Science 220, 671–680, https://doi.org/10.1126/science.220.4598.671 (1983). · DOI · Paper page
  2. Hukushima, K. & Nemoto, K. Exchange monte carlo method and application to spin glass simulations. Journal of the Physical Society of Japan 65, 1604–1608, https://doi.org/10.1143/JPSJ.65.1604 (1996). · DOI · Paper page
  3. Monasson, R. & Zecchina, R. Statistical mechanics of the random k -satisfiability model. Phys. Rev. E 56, 1357–1370, https://doi.org/10.1103/PhysRevE.56.1357 (1997). · DOI
  4. Monasson, R. Optimization problems and replica symmetry breaking in finite connectivity spin glasses. Journal of Physics A: Mathematical and General 31, 513 (1998). · doi:10.1088/0305-4470/31/2/012
  5. Mezard, M. & Montanari, A. Information, Physics, and Computation (Oxford University Press, Inc., New York, NY, USA, 2009).
  6. Suzuki, S. & Okada, M. Residual energies after slow quantum annealing. J. Phys. Soc. Jpn. 74, 1649–1652, https://doi.org/10.1143/JPSJ.74.1649 (2005). · DOI · Paper page
  7. Ohzeki, M. & Nishimori, H. Quantum annealing: An introduction and new developments. J. Comput. Theor. Nanosci. 8, 963–971, https://doi.org/10.1166/jctn.2011.1776963 (2011-06-01T00:00:00). · DOI · Paper page
  8. Santoro, G. E., Martoňák, R., Tosatti, E. & Car, R. Theory of quantum annealing of an ising spin glass. Sci. 295, 2427–2430, https://doi.org/10.1126/science.1068774 (2002). · DOI · Paper page
  9. Martoňák, R., Santoro, G. E. & Tosatti, E. Quantum annealing of the traveling-salesman problem. Phys. Rev. E 70, 057701, https://doi.org/10.1103/PhysRevE.70.057701 (2004). · DOI · Paper page
  10. Baldassi, C. & Zecchina, R. Efficiency of quantum vs. classical annealing in nonconvex learning problems. Proc. Nat. Acad. Sci. 115, 1457–1462, https://doi.org/10.1073/pnas.1711456115 (2018). · DOI · Paper page
  11. Johnson, M. W. et al. A scalable control system for a superconducting adiabatic quantum optimization processor. Supercond. Sci. Technol. 23, 065004 (2010). · DOI · Paper page
  12. Berkley, A. J. et al. A scalable readout system for a superconducting adiabatic quantum optimization system. Supercond. Sci. Technol. 23, 105014 (2010). · DOI · Paper page
  13. Harris, R. et al. Experimental investigation of an eight-qubit unit cell in a superconducting optimization processor. Phys. Rev. B 82, 024511, https://doi.org/10.1103/PhysRevB.82.024511 (2010). · DOI · Paper page
  14. Bunyk, P. I. et al. Architectural considerations in the design of a superconducting quantum annealing processor. IEEE Transactions on Appl. Supercond. 24, 1–10, https://doi.org/10.1109/TASC.2014.2318294 (2014). · DOI · Paper page
  15. Amin, M. H. Searching for quantum speedup in quasistatic quantum annealers. Phys. Rev. A 92, 052323 (2015). · DOI · Paper page
  16. Ohzeki, M. Quantum annealing with the jarzynski equality. Phys. Rev. Lett. 105, 050401, https://doi.org/10.1103/PhysRevLett.105.050401 (2010). · DOI
  17. Ohzeki, M., Nishimori, H. & Katsuda, H. Nonequilibrium work on spin glasses in longitudinal and transverse fields. J. Phys. Soc. Jpn. 80, 084002, https://doi.org/10.1143/JPSJ.80.084002 (2011). · DOI
  18. Ohzeki, M. & Nishimori, H. Nonequilibrium work performed in quantum annealing. J. Physics: Conf. Ser. 302, 012047 (2011).
  19. Kadowaki, T. & Ohzeki, M. Experimental and theoretical study of thermodynamic effects in a quantum annealer. J. Phys. Soc. Jpn. 88, 061008, https://doi.org/10.7566/JPSJ.88.061008 (2019). · DOI · Paper page
  20. Rosenberg, G. et al. Solving the optimal trading trajectory problem using a quantum annealer. J. Sel. Top. Signal Process. 10, 1053–1060, https://doi.org/10.1109/JSTSP.2016.2574703 (2016). · DOI · Paper page
  21. Hernandez, M. & Aramon, M. Enhancing quantum annealing performance for the molecular similarity problem. Quantum Inf. Process. 16, 133, https://doi.org/10.1007/s11128-017-1586-y (2017). · DOI · Paper page
  22. Venturelli, D., Marchand, D. J. J. & Rojo, G. Quantum Annealing Implementation of Job-Shop Scheduling. ArXiv e-prints 1506.08479 (2015). · arXiv
  23. Neukart, F. et al. Traffic flow optimization using a quantum annealer. Front. ICT 4, 29 (2017). · DOI · Paper page
  24. Henderson, M., Novak, J. & Cook, T. Leveraging Adiabatic Quantum Computation for Election Forecasting. ArXiv e-prints 1802.00069 (2018). · arXiv
  25. Arai, S., Ohzeki, M. & Tanaka, K. Deep neural network detects quantum phase transition. J. Phys. Soc. Jpn. 87, 033001, https://doi.org/10.7566/JPSJ.87.033001 (2018). · DOI
  26. Takahashi, C. et al. Statistical-mechanical analysis of compressed sensing for hamiltonian estimation of ising spin glass. J. Phys. Soc. Jpn. 87, 074001, https://doi.org/10.7566/JPSJ.87.074001 (2018). · DOI
  27. Ohzeki, M. et al. Quantum annealing: next-generation computation and how to implement it when information is missing. Nonlinear Theory and Its Appl., IEICE 9, 392–405, https://doi.org/10.1587/nolta.9.392 (2018). · DOI
  28. Neukart, F., VonDollen, D., Seidel, C. & Compostella, G. Quantum-enhanced reinforcement learning for finite-episode games with discrete state spaces. Front. Phys. 5, 71, https://doi.org/10.3389/fphy.2017.00071 (2018). · DOI
  29. Khoshaman, A., Vinci, W., Denis, B., Andriyash, E. & Amin, M. H. Quantum variational autoencoder. Quantum Sci. Technol. 4, 014001 (2018). · DOI · Paper page
  30. Ohzeki, M., Miki, A., Miyama, M. J. & Terabe, M. Control of automated guided vehicles without collision by quantum annealer and digital devices. Front. Comput. Sci. 1, 9, https://doi.org/10.3389/fcomp.2019.00009 (2019). · DOI · Paper page
  31. Okada, S., Ohzeki, M., Terabe, M. & Taguchi, S. Improving solutions by embedding larger subproblems in a d-wave quantum annealer. Sci. Reports 9, 2098, https://doi.org/10.1038/s41598-018-38388-4 (2019). · DOI · Paper page
  32. Okada, S., Ohzeki, M. & Tanaka, K. The efficient quantum and simulated annealing of Potts models using a half-hot constraint. arXiv e-prints arXiv:1904.01522 (2019). · DOI
  33. Okada, S., Ohzeki, M. & Taguchi, S. Efficient partition of integer optimization problems with one-hot encoding. Sci. Reports 9, 13036, https://doi.org/10.1038/s41598-019-49539-6 (2019). · DOI · Paper page
  34. Seki, Y. & Nishimori, H. Quantum annealing with antiferromagnetic fluctuations. Phys. Rev. E 85, 051112, https://doi.org/10.1103/PhysRevE.85.051112 (2012). · DOI · Paper page
  35. Seki, Y. & Nishimori, H. Quantum annealing with antiferromagnetic transverse interactions for the hopfield model. J. Phys. A: Math. Theor. 48, 335301 (2015). · DOI · Paper page
  36. Ohzeki, M. Quantum monte carlo simulation of a particular class of non-stoquastic hamiltonians in quantum annealing. Sci. Reports 7, 41186 (2017). · DOI
  37. Arai, S., Ohzeki, M. & Tanaka, K. Dynamics of Order Parameters of Non-stoquastic Hamiltonians in the Adaptive Quantum Monte Carlo Method. ArXiv e-prints 1810.09943 (2018). · DOI
  38. Okada, S., Ohzeki, M. & Tanaka, K. Phase diagrams of one-dimensional ising and xy models with fully connected ferromagnetic and anti-ferromagnetic quantum fluctuations. J. Phys. Soc. Jpn. 88, 024802, https://doi.org/10.7566/JPSJ.88.024802 (2019). · DOI
  39. Stratonovich, R. L. On a Method of Calculating Quantum Distribution Functions. Sov. Phys. Doklady 2, 416 (1957).
  40. Hubbard, J. Calculation of partition functions. Phys. Rev. Lett. 3, 77–78, https://doi.org/10.1103/PhysRevLett.3.77 (1959). · DOI · Paper page
  41. Yamaoka, M. et al. A 20k-spin ising chip to solve combinatorial optimization problems with cmos annealing. IEEE J. Solid-State Circuits 51, 303–309, https://doi.org/10.1109/JSSC.2015.2498601 (2016). · DOI · Paper page
  42. Tsukamoto, S., Takatsu, M., Matsubara, S. & Tamura, H. An accelerator architecture for combinatorial optimization problems. In FUJITSU Sci. Tech. J., vol. 53, 8 (2017).
  43. Suzuki, M. Relationship between d-dimensional quantal spin systems and (d . 1)-dimensional ising systems: Equivalence, critical exponents and systematic approximants of the partition function and spin correlations. Prog. Theor. Phys. 56, 1454–1469, https://doi.org/10.1143/PTP.56.1454 (1976). · DOI · Paper page
  44. Ohzeki, M. Message-passing algorithm of quantum annealing with nonstoquastic hamiltonian. J. Phys. Soc. Jpn. 88, 061005, https://doi.org/10.7566/JPSJ.88.061005 (2019). · DOI
  45. White, S. R. et al. Numerical study of the two-dimensional hubbard model. Phys. Rev. B 40, 506–516, https://doi.org/10.1103/PhysRevB.40.506 (1989). · DOI · Paper page
  46. Neven, H., Denchev, V. S., Rose, G. & Macready, W. G. Qboost: Large scale classifier training withadiabatic quantum optimization. In Hoi, S. C. H. & Buntine, W. (eds.) Proceedings of the Asian Conference on Machine Learning, vol. 25 of Proceedings of Machine Learning Research, 333–348 (PMLR, Singapore Management University, Singapore, 2012).
  47. Hen, I. & Sarandy, M. S. Driver hamiltonians for constrained optimization in quantum annealing. Phys. Rev. A 93, 062312, https://doi.org/10.1103/PhysRevA.93.062312 (2016). · DOI · Paper page
  48. Tanaka, T. A statistical-mechanics approach to large-system analysis of cdma multiuser detectors. IEEE Trans. Inf. Theor. 48, 2888–2910 (2006). · DOI · Paper page
  49. Boeing, G. Osmnx: New methods for acquiring, constructing, analyzing, and visualizing complex street networks. Comput. Environ. Urban Syst. 65, 126–139, https://doi.org/10.1016/j.compenvurbsys.2017.05.004 (2017). · DOI · Paper page

Cited by

See all 64

Metadata

Authors
Ohzeki, M.
Venue
Scientific Reports
Published
2020-02-20
Volume
10
Issue
1
Pages
3126-3126
ISSN
2045-2322 (ISSN-L)
OpenAlex
W3006355565
Cited by
64
References
7
FWCI
2.65
Type
journal article
Language
en
Open access
gold
Licence
Funders
  • MEXT | Japan Society for the Promotion of Science (19H01095)
  • Next Generation High-Performance Computing Infrastructures and Applications R\&D Program by MEXT

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: Breaking limitation of quantum annealer in solving optimization problems under constraints. https://app.cochat.ai/papers/10.1038/s41598-020-60022-5
The paper
Ohzeki, M. (2020). Breaking limitation of quantum annealer in solving optimization problems under constraints. Scientific Reports. https://doi.org/10.1038/s41598-020-60022-5

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.