Breaking limitation of quantum annealer in solving optimization problems under constraints
Open accessThe 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.
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
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
Mathematical foundation of quantum annealing
Morita, S., & Nishimori, H. (2008) · Journal of Mathematical Physics · doi:10.1063/1.2995837 · Cited by 381
Finding low-energy conformations of lattice protein models by quantum annealing
Perdomo-Ortiz, A., Dickson, N., Drew-Brook, M., Rose, G., & Aspuru-Guzik, A. (2012) · Scientific Reports · doi:10.1038/srep00571 · Cited by 366
Li, R. Y., Di Felice, R., Rohs, R., & Lidar, D. A. (2018) · npj Quantum Information · doi:10.1038/s41534-018-0060-8 · Cited by 202 · cited 1×
“∑ ∑ ∑ ν λ = − + − μ μ μ μ μ ( ) H h q q q ( , ) 2 1 , (26) i i i i i , , , , 2”
Quantum Speedup by Quantum Annealing
Somma, R. D., Nagaj, D., & Kieferová, M. (2012) · Physical Review Letters · doi:10.1103/physrevlett.109.050501 · Cited by 176
Quantum Annealing for Constrained Optimization
Hen, I., & Spedalieri, F. M. (2016) · Physical Review Applied · doi:10.1103/physrevapplied.5.034007 · Cited by 114
Reinforcement Learning Using Quantum Boltzmann Machines
Crawford, D., Levit, A., Ghadermarzy, N., Oberoi, J. S., & Ronagh, P. (2016) · arXiv · doi:10.48550/arxiv.1612.05695 · Cited by 14
Research works printed but not linked: 49
- 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
- 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
- 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
- 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
- Mezard, M. & Montanari, A. Information, Physics, and Computation (Oxford University Press, Inc., New York, NY, USA, 2009).
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- Amin, M. H. Searching for quantum speedup in quasistatic quantum annealers. Phys. Rev. A 92, 052323 (2015). · DOI · Paper page
- Ohzeki, M. Quantum annealing with the jarzynski equality. Phys. Rev. Lett. 105, 050401, https://doi.org/10.1103/PhysRevLett.105.050401 (2010). · DOI
- 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
- Ohzeki, M. & Nishimori, H. Nonequilibrium work performed in quantum annealing. J. Physics: Conf. Ser. 302, 012047 (2011).
- 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
- 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
- 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
- Venturelli, D., Marchand, D. J. J. & Rojo, G. Quantum Annealing Implementation of Job-Shop Scheduling. ArXiv e-prints 1506.08479 (2015). · arXiv
- Neukart, F. et al. Traffic flow optimization using a quantum annealer. Front. ICT 4, 29 (2017). · DOI · Paper page
- Henderson, M., Novak, J. & Cook, T. Leveraging Adiabatic Quantum Computation for Election Forecasting. ArXiv e-prints 1802.00069 (2018). · arXiv
- 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
- 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
- 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
- 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
- Khoshaman, A., Vinci, W., Denis, B., Andriyash, E. & Amin, M. H. Quantum variational autoencoder. Quantum Sci. Technol. 4, 014001 (2018). · DOI · Paper page
- 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
- 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
- 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
- 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
- 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
- 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
- Ohzeki, M. Quantum monte carlo simulation of a particular class of non-stoquastic hamiltonians in quantum annealing. Sci. Reports 7, 41186 (2017). · DOI
- 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
- 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
- Stratonovich, R. L. On a Method of Calculating Quantum Distribution Functions. Sov. Phys. Doklady 2, 416 (1957).
- Hubbard, J. Calculation of partition functions. Phys. Rev. Lett. 3, 77–78, https://doi.org/10.1103/PhysRevLett.3.77 (1959). · DOI · Paper page
- 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
- Tsukamoto, S., Takatsu, M., Matsubara, S. & Tamura, H. An accelerator architecture for combinatorial optimization problems. In FUJITSU Sci. Tech. J., vol. 53, 8 (2017).
- 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
- 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
- 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
- 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).
- 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
- 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
- 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
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
“By considering the partition function of the QUBO cost function and employing a Hubbard–Stratonovich transformation for the quadratic constraints P 2 k followed by a Wick rotation in the auxiliary variables, an alternative cost function can be derived (see the original works [139, 197] for details).”
Montañez-Barrera, J. A., Willsch, D., Maldonado-Romo, A., & Michielsen, K. (2024) · Quantum Science and Technology · doi:10.1088/2058-9565/ad35e4 · Cited by 57
“There are three main reasons for this; first, many combinatorial optimization problems can be encoded in Hamiltonians, the ground state being the optimal solution of the problem [1, 2]; second, they are commonly hard to solve and have practical applications [3]; and third, the quantum algorithms to solve these problem…”
BackgroundBenchmark Test of Black-box Optimization Using D-Wave Quantum Annealer
Koshikawa, A. S., Ohzeki, M., Kadowaki, T., & Tanaka, K. (2021) · Journal of the Physical Society of Japan · doi:10.7566/jpsj.90.064001 · Cited by 43
Self-citationMontañez-Barrera, J. A., & Michielsen, K. (2025) · npj Quantum Information · doi:10.1038/s41534-025-01082-1 · Cited by 34
Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study
Gemeinhardt, F., Garmendia, A., Wimmer, M., Weder, B., & Leymann, F. (2024) · ACM Computing Surveys · doi:10.1145/3620668 · Cited by 22
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
- creativecommons.org/licenses/by/4.0 (tdm)
- creativecommons.org/licenses/by/4.0 (vor)
- 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.