Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Quantum Information Processing
Published in: Quantum Information Processing 7/2023

01-07-2023 | Regular Article

Solving MaxCut with quantum imaginary time evolution

Authors: Rizwanul Alam, George Siopsis, Rebekah Herrman, James Ostrowski, Phillip C. Lotshaw, Travis S. Humble

Published in: Quantum Information Processing | Issue 7/2023

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We introduce a method to solve the MaxCut problem efficiently based on quantum imaginary time evolution (QITE). We employ a linear Ansatz for unitary updates and an initial state involving no entanglement, as well as an imaginary-time-dependent Hamiltonian interpolating between a given graph and a subgraph with two edges excised. We apply the method to thousands of randomly selected graphs with up to fifty vertices. We show that our algorithm exhibits a 93% and above performance converging to the maximum solution of the MaxCut problem for all considered graphs. Our results compare favorably with the performance of classical algorithms, such as the greedy and Goemans–Williamson algorithms. We also discuss the overlap of the final state of the QITE algorithm with the ground state as a performance metric, which is a quantum feature not shared by other classical algorithms.
previous article Security analysis for single-state circular mediated semi-quantum key distribution
next article Quantum circuit implementations of SM4 block cipher based on different gate sets

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
Literature
1.
Arute, F., Arya, K., Babbush, R., Bacon, D., Bardin, J.C., Barends, R., Biswas, R., Boixo, S., Brandao, F.G.S.L., Buell, D.A., et al.: Quantum supremacy using a programmable superconducting processor. Nature 574(7779), 505–510 (2019)ADSCrossRef
2.
Zhong, H.-S., Wang, H., Deng, Y.-H., Chen, M.-C., Peng, L.-C., Luo, Y.-H., Qin, J., Wu, D., Ding, X., Hu, Y., Hu, P., Yang, X.-Y., Zhang, W.-J., Li, H., Li, Y., Jiang, X., Gan, L., Yang, G., You, L., Wang, Z., Li, L., Liu, N.-L., Lu, C.-Y., Pan, J.-W.: Quantum computational advantage using photons. Science 370, 6523 (2020)CrossRef
3.
Festa, P., Pardalos, P.M., Resende, M.G.C., Ribeiro, C.C.: Randomized heuristics for the MAX-CUT problem. Optim. Methods Softw. 17(6), 1033–1058 (2002)MathSciNetCrossRefMATH
4.
Schröder, H., May, A.E., Vrt’o, I., Sýkora, O.: Approximation algorithms for the vertex bipartization problem. In: Plášil, F., Jeffery, K.G. (eds.) SOFSEM’97: Theory and Practice of Informatics, pp. 547–554 (1997). Springer, Berlin
5.
Kahruman, S., Kolotoglu, E., Butenko, S., Hicks, I.: On greedy construction heuristics for the max-cut problem. Int. J. Comput. Sci. Eng. 1, 04 (2007)
6.
Mathieu, C., Schudy, W.: Yet another algorithm for dense max cut: Go greedy. In: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’08, pp. 176–182, USA, (2008). Society for Industrial and Applied Mathematics
7.
Bian, Y., Gronskiy, A., Buhmann, J.M.: Greedy MaxCut algorithms and their information content. In: 2015 IEEE Information Theory Workshop (ITW), pp. 1–5 (2015)
8.
Goemans, M.X., Williamson, D.P.: 879-approximation algorithms for max cut and max 2sat. In: Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, pp. 422–431 (1994)
9.
10.
Wang, Z., Hadfield, S., Jiang, Z., Rieffel, E.G.: Quantum approximate optimization algorithm for MaxCut: a fermionic view. Phys. Rev. A 97(2), 022304 (2018)ADSCrossRef
11.
12.
Zhou, L., Wang, S.-T., Choi, S., Pichler, H., Lukin, M.D.: Quantum approximate optimization algorithm: performance, mechanism, and implementation on near-term devices. Phys. Rev. X 10, 021067 (2020)
13.
Guerreschi, G.G., Matsuura, A.Y.: QAOA for Max-Cut requires hundreds of qubits for quantum speed-up. Sci. Rep. 9, 6903 (2019)ADSCrossRef
14.
Medvidović, M., Carleo, G.: Classical variational simulation of the quantum approximate optimization algorithm. npj Quantum Inf. 7(1), 1–7 (2021)CrossRef
15.
Brandão, F.G.S.L., Broughton, M., Farhi, E., Gutmann, S., Neven, H.: For fixed control parameters the quantum approximate optimization algorithm’s objective function value concentrates for typical instances. arXiv preprint arXiv:​1812.​04170 (2018)
16.
Wurtz, J., Love, P.: Maxcut quantum approximate optimization algorithm performance guarantees for \(p>1\). Phys. Rev. A 103, 042612 (2021)ADSMathSciNetCrossRef
17.
Shaydulin, R., Alexeev, Y.: Evaluating quantum approximate optimization algorithm: a case study. In: 2019 Tenth International Green and Sustainable Computing Conference (IGSC), pp. 1–6 (2019)
18.
Crooks, G.E.: Performance of the quantum approximate optimization algorithm on the maximum cut problem. arXiv preprint arXiv:​1811.​08419 (2018)
19.
Shaydulin, R., Hadfield, S., Hogg, T., Safro, I.: Classical symmetries and the quantum approximate optimization algorithm. Quantum Inf. Process. 20(11), 359 (2021)ADSMathSciNetCrossRefMATH
20.
Herrman, R., Ostrowski, J., Humble, T.S., Siopsis, G.: Lower bounds on circuit depth of the quantum approximate optimization algorithm. Quantum Inf. Process. 20(2), 1–17 (2021)MathSciNetCrossRefMATH
21.
Akshay, V., Philathong, H., Morales, M.E.S., Biamonte, J.D.: Reachability deficits in quantum approximate optimization. Phys. Rev. Lett. 124, 090504 (2020)ADSMathSciNetCrossRef
22.
23.
Pagano, G., Bapat, A., Becker, P., Collins, K.S., De, A., Hess, P.W., Kaplan, H.B., Kyprianidis, A., Tan, W.L., Baldwin, C., Brady, L.T., Deshpande, A., Liu, F., Jordan, S., Gorshkov, A.V., Monroe, C.: Quantum approximate optimization of the long-range Ising model with a trapped-ion quantum simulator. Proc. Natl. Acad. Sci. 117(41), 25396–25401 (2020)ADSMathSciNetCrossRef
24.
Wang, Z., Rubin, N.C., Dominy, J.M., Rieffel, E.G.: \(XY\)-mixers: analytical and numerical results for the quantum alternating operator ansatz. Phys. Rev. A 101, 012320 (2020)ADSMathSciNetCrossRef
25.
Zhu, L., Tang, H.L., Barron, G.S., Mayhall, N.J., Barnes, E., Economou, S.E.: An adaptive quantum approximate optimization algorithm for solving combinatorial problems on a quantum computer. arXiv preprint arXiv:​2005.​10258 (2020)
26.
Jiang, Z., Rieffel, E.G., Wang, Z.: Near-optimal quantum circuit for Grover’s unstructured search using a transverse field. Phys. Rev. A 95, 062317 (2017)ADSCrossRef
27.
Bärtschi, A., Eidenbenz, S.: Grover mixers for QAOA: Shifting complexity from mixer design to state preparation. arXiv preprint arXiv:​2006.​00354v2 (2020)
28.
Cook, J., Eidenbenz, S., Bärtschi, A.: The quantum alternating operator ansatz on maximum \(k\)-vertex cover. arXiv preprint arXiv:​1910.​13483v2 (2020)
29.
Li, L., Fan, M., Coram, M., Riley, P., Leichenauer, S.: Quantum optimization with a novel Gibbs objective function and ansatz architecture search. Phys. Rev. Res. 2, 023074 (2020)CrossRef
30.
Tate, R., Farhadi, M., Herold, C., Mohler, G., Gupta, S.: Bridging classical and quantum with SDP initialized warm-starts for QAOA. arXiv preprint arXiv:​2010.​14021 (2020)
31.
Herrman, R., Lotshaw, P.C., Ostrowski, J., Humble, T.S., Siopsis, G.: Multi-angle quantum approximate optimization algorithm. Sci. Rep. 12(1), 6781 (2022)ADSCrossRef
32.
33.
Bapat, A., Jordan, S.P.: Approximate optimization of the MaxCut problem with a local spin algorithm. Phys. Rev. A 103, 052413 (2021)ADSMathSciNetCrossRef
34.
Marwaha, K.: Local classical MAX-CUT algorithm outperforms \(p=2\) QAOA on high-girth regular graphs. Quantum 5, 437 (2021)CrossRef
35.
Marwaha, K., Hadfield, S.: Bounds on approximating Max \(k\)XOR with quantum and classical local algorithms. Quantum 6, 757 (2022)CrossRef
36.
McArdle, S., Jones, T., Endo, S., Li, Y., Benjamin, S.C., Yuan, X.: Variational ansatz-based quantum simulation of imaginary time evolution. npj Quantum Inf. 5(1), 75 (2019)ADSCrossRef
37.
Beach, M.J.S., Melko, R.G., Grover, T., Hsieh, T.H.: Making trotters sprint: a variational imaginary time ansatz for quantum many-body systems. Phys. Rev. B 100(9), 094434 (2019)ADSCrossRef
38.
Love, P.J.: Cooling with imaginary time. Nat. Phys. 16(2), 130–131 (2020)CrossRef
39.
Motta, M., Sun, C., Tan, A.T.K., O’Rourke, M.J., Ye, E., Minnich, A.J., Brandao, F.G.S.L., Chan, G.K.-L.: Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution. Nat. Phys. 16(2), 205–210 (2020)CrossRef
40.
Gomes, N., Zhang, F., Berthusen, N.F., Wang, C.-Z., Ho, K.-M., Orth, P.P., Yao, Y.: Efficient step-merged quantum imaginary time evolution algorithm for quantum chemistry. J. Chem. Theory Comput. 16(10), 6256–6266 (2020)CrossRef
41.
Yeter-Aydeniz, K., Pooser, R.C., Siopsis, G.: Practical quantum computation of chemical and nuclear energy levels using quantum imaginary time evolution and lanczos algorithms. npj Quantum Inf. 6(1), 1–8 (2020)CrossRef
42.
Yeter-Aydeniz, K., Gard, B.T., Jakowski, J., Majumder, S., Barron, G.S., Siopsis, G., Humble, T.S., Pooser, R.C.: Benchmarking quantum chemistry computations with variational, imaginary time evolution, and Krylov space solver algorithms. Adv. Quantum Technol. 2100012 (2021)
43.
Barison, S., Galli, D.E., Motta, M.: Quantum simulations of molecular systems with intrinsic atomic orbitals. arXiv e-prints, page arXiv:​2011.​08137 November (2020)
44.
Kamakari, H., Sun, S.-N., Motta, M., Minnich, A.J.: Digital quantum simulation of open quantum systems using quantum imaginary time evolution. arXiv preprint arXiv:​2104.​07823 (2021)
45.
Ville, J.-L., Morvan, A., Hashim, A., Naik, R.K., Mitchell, B., Kreikebaum, J.-M., O’Brien, K.P., Wallman, J.J., Hincks, I.: Joseph Emerson, et al. Leveraging randomized compiling for the qite algorithm. arXiv preprint arXiv:​2104.​08785 (2021)
46.
Cao, C., An, Z., Hou, S.-Y., Zhou, D.L., Zeng, B.: Quantum imaginary time evolution steered by reinforcement learning (2021)
47.
Nishi, H., Kosugi, T., Matsushita, Y.: Implementation of quantum imaginary-time evolution method on NISQ devices by introducing nonlocal approximation. npj Quantum Inf. 7(1), 85 (2021)ADSCrossRef
48.
Lin, S.-H., Dilip, R., Green, A.G., Smith, A., Pollmann, F.: Real- and imaginary-time evolution with compressed quantum circuits. PRX Quantum 2, 010342 (2021)CrossRef
49.
Hadfield, S., Wang, Z., O’Gorman, B., Rieffel, E.G., Venturelli, D., Biswas, R.: From the quantum approximate optimization algorithm to a quantum alternating operator ansatz. Algorithms 12(2), 34 (2019)MathSciNetCrossRefMATH
Metadata
Title
Solving MaxCut with quantum imaginary time evolution
Authors
Rizwanul Alam
George Siopsis
Rebekah Herrman
James Ostrowski
Phillip C. Lotshaw
Travis S. Humble
Publication date
01-07-2023
Publisher
Springer US
Published in
Quantum Information Processing / Issue 7/2023
Print ISSN: 1570-0755
Electronic ISSN: 1573-1332
DOI
https://doi.org/10.1007/s11128-023-04045-7

Other articles of this Issue 7/2023

Quantum Information Processing 7/2023 Go to the issue

OriginalPaper

A doubly stochastic matrices-based approach to optimal qubit routing

OriginalPaper

A universal quantum algorithm for weighted maximum cut and Ising problems

Correction

Correction: A quantum vocal theory of sound

OriginalPaper

Quantum circuits for hyperelliptic curve discrete logarithms over the Mersenne prime fields

OriginalPaper

Ground-state and thermal entanglements in non-Hermitian XY system with real and imaginary magnetic fields

Regular Article

Multipartite entanglement detection via correlation minor norm