{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,10,23]],"date-time":"2024-10-23T23:40:03Z","timestamp":1729726803115,"version":"3.28.0"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2023,7,11]],"date-time":"2023-07-11T00:00:00Z","timestamp":1689033600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,7,11]],"date-time":"2023-07-11T00:00:00Z","timestamp":1689033600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004168","name":"Universit\u00e4t zu L\u00fcbeck","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004168","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004168","name":"Universit\u00e4t zu L\u00fcbeck","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100004168","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Quantum Inf Process"],"abstract":"Abstract<\/jats:title>We propose a hybrid quantum-classical algorithm to compute approximate solutions of binary combinatorial problems. We employ a shallow-depth quantum circuit to implement a unitary and Hermitian operator that block-encodes the weighted maximum cut or the Ising Hamiltonian. Measuring the expectation of this operator on a variational quantum state yields the variational energy of the quantum system. The system is enforced to evolve toward the ground state of the problem Hamiltonian by optimizing a set of angles using normalized gradient descent. Experimentally, our algorithm outperforms the state-of-the-art quantum approximate optimization algorithm on random fully connected graphs and challenges D-Wave quantum annealers by producing good approximate solutions. Source code and data files are publicly available (https:\/\/github.com\/nkuetemeli\/UQMaxCutAndIsing<\/jats:ext-link>).<\/jats:p>","DOI":"10.1007\/s11128-023-04025-x","type":"journal-article","created":{"date-parts":[[2023,7,11]],"date-time":"2023-07-11T08:02:04Z","timestamp":1689062524000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A universal quantum algorithm for weighted maximum cut and Ising problems"],"prefix":"10.1007","volume":"22","author":[{"ORCID":"http:\/\/orcid.org\/0009-0001-9989-1012","authenticated-orcid":false,"given":"Natacha","family":"Kuete Meli","sequence":"first","affiliation":[]},{"ORCID":"http:\/\/orcid.org\/0000-0001-9042-0428","authenticated-orcid":false,"given":"Florian","family":"Mannel","sequence":"additional","affiliation":[]},{"ORCID":"http:\/\/orcid.org\/0000-0002-5243-0331","authenticated-orcid":false,"given":"Jan","family":"Lellmann","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,7,11]]},"reference":[{"key":"4025_CR1","unstructured":"D-Wave Systems: QPU Solver Datasheet. https:\/\/docs.dwavesys.com\/docs\/latest\/doc_qpu.html (2022)"},{"key":"4025_CR2","doi-asserted-by":"crossref","unstructured":"Benkner, M.S., L\u00e4hner, Z., Golyanik, V., Wunderlich, C., Theobalt, C., Moeller, M.: Q-match: iterative shape matching via quantum annealing. In: Proceedings of the IEEE\/CVF International Conference on Computer Vision, pp. 7586\u20137596 (2021)","DOI":"10.1109\/ICCV48922.2021.00749"},{"key":"4025_CR3","doi-asserted-by":"crossref","unstructured":"Kuete\u00a0Meli, N., Mannel, F., Lellmann, J.: An iterative quantum approach for transformation estimation from point sets. In: Computer Vision and Pattern Recognition, pp. 529\u2013537 (2022)","DOI":"10.1109\/CVPR52688.2022.00061"},{"key":"4025_CR4","doi-asserted-by":"crossref","unstructured":"Groppe, S., Groppe, J.: Optimizing transaction schedules on universal quantum computers via code generation for Grover\u2019s search algorithm. In: Proceedings of the 25th International Database Engineering & Applications Symposium, pp. 149\u2013156 (2021)","DOI":"10.1145\/3472163.3472164"},{"key":"4025_CR5","unstructured":"Uotila, V.J.E.: Synergy between quantum computers and databases. In: Proceedings of the VLDB 2022 PhD Workshop Co-located with the 48th International Conference on Very Large Databases (VLDB 2022) (2022)"},{"issue":"6","key":"4025_CR6","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1147\/rd.176.0525","volume":"17","author":"CH Bennett","year":"1973","unstructured":"Bennett, C.H.: Logical reversibility of computation. IBM J. Res. Dev. 17(6), 525\u2013532 (1973)","journal-title":"IBM J. Res. Dev."},{"issue":"2","key":"4025_CR7","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1137\/S0036144598347011","volume":"41","author":"PW Shor","year":"1999","unstructured":"Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Rev. 41(2), 303\u2013332 (1999)","journal-title":"SIAM Rev."},{"key":"4025_CR8","doi-asserted-by":"crossref","unstructured":"Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, pp. 212\u2013219 (1996)","DOI":"10.1145\/237814.237866"},{"key":"4025_CR9","volume-title":"The Two-Dimensional Ising Model","author":"BM McCoy","year":"2014","unstructured":"McCoy, B.M., Wu, T.T.: The Two-Dimensional Ising Model. Courier Corporation, Cambridge (2014)"},{"issue":"6","key":"4025_CR10","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"MX Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM (JACM) 42(6), 1115\u20131145 (1995)","journal-title":"J. ACM (JACM)"},{"key":"4025_CR11","doi-asserted-by":"publisher","first-page":"5","DOI":"10.3389\/fphy.2014.00005","volume":"2","author":"A Lucas","year":"2014","unstructured":"Lucas, A.: Ising formulations of many np problems. Front. Phys. 2, 5 (2014)","journal-title":"Front. Phys."},{"issue":"2","key":"4025_CR12","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1109\/TPAMI.2004.1262177","volume":"26","author":"V Kolmogorov","year":"2004","unstructured":"Kolmogorov, V., Zabin, R.: What energy functions can be minimized via graph cuts? IEEE Trans. Pattern Anal. Mach. Intell. 26(2), 147\u2013159 (2004)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"4025_CR13","doi-asserted-by":"crossref","unstructured":"Ding, C.H., He, X., Zha, H., Gu, M., Simon, H.D.: A min-max cut algorithm for graph partitioning and data clustering. In: Proceedings 2001 IEEE International Conference on Data Mining, pp. 107\u2013114 (2001)","DOI":"10.1109\/ICDM.2001.989507"},{"issue":"3","key":"4025_CR14","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1287\/opre.36.3.493","volume":"36","author":"F Barahona","year":"1988","unstructured":"Barahona, F., Gr\u00f6tschel, M., J\u00fcnger, M., Reinelt, G.: An application of combinatorial optimization to statistical physics and circuit layout design. Oper. Res. 36(3), 493\u2013513 (1988)","journal-title":"Oper. Res."},{"issue":"1","key":"4025_CR15","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1103\/revmodphys.90.015002","volume":"90","author":"T Albash","year":"2018","unstructured":"Albash, T., Lidar, D.A.: Adiabatic quantum computation. Rev. Mod. Phys. 90(1), 25 (2018). https:\/\/doi.org\/10.1103\/revmodphys.90.015002","journal-title":"Rev. Mod. Phys."},{"issue":"10","key":"4025_CR16","doi-asserted-by":"publisher","DOI":"10.1063\/1.2798382","volume":"48","author":"S Jansen","year":"2007","unstructured":"Jansen, S., Ruskai, M.-B., Seiler, R.: Bounds for the adiabatic approximation with applications to quantum computation. J. Math. Phys. 48(10), 102111 (2007). https:\/\/doi.org\/10.1063\/1.2798382","journal-title":"J. Math. Phys."},{"issue":"833","key":"4025_CR17","first-page":"696","volume":"137","author":"C Zener","year":"1932","unstructured":"Zener, C.: Non-adiabatic crossing of energy levels. Proc. R. Soc. Lond. Ser. A Contain. Pap. Math. Phys. Character 137(833), 696\u2013702 (1932)","journal-title":"Proc. R. Soc. Lond. Ser. A Contain. Pap. Math. Phys. Character"},{"issue":"2","key":"4025_CR18","doi-asserted-by":"publisher","first-page":"593","DOI":"10.1137\/120871997","volume":"42","author":"R Somma","year":"2013","unstructured":"Somma, R., Boixo, S.: Spectral gap amplification. SIAM J. Comput. 42(2), 593\u2013610 (2013)","journal-title":"SIAM J. Comput."},{"key":"4025_CR19","unstructured":"Farhi, E., Goldstone, J., Gutmann, S.: A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028 (2014)"},{"issue":"1","key":"4025_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1038\/s41598-019-43176-9","volume":"9","author":"GG Guerreschi","year":"2019","unstructured":"Guerreschi, G.G., Matsuura, A.Y.: QAOA for Max-Cut requires hundreds of qubits for quantum speed-up. Sci. Rep. 9(1), 1\u20137 (2019)","journal-title":"Sci. Rep."},{"issue":"2","key":"4025_CR21","doi-asserted-by":"publisher","first-page":"34","DOI":"10.3390\/a12020034","volume":"12","author":"S Hadfield","year":"2019","unstructured":"Hadfield, S., Wang, Z., O\u2019Gorman, 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)","journal-title":"Algorithms"},{"issue":"2","key":"4025_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s11128-021-03001-7","volume":"20","author":"R Herrman","year":"2021","unstructured":"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\u201317 (2021)","journal-title":"Quantum Inf. Process."},{"key":"4025_CR23","doi-asserted-by":"crossref","unstructured":"Shaydulin, R., Alexeev, Y.: Evaluating quantum approximate optimization algorithm: a case study. In: 2019 Tenth International Green and Sustainable Computing Conference (IGSC), pp. 1\u20136 (2019)","DOI":"10.1109\/IGSC48788.2019.8957201"},{"key":"4025_CR24","doi-asserted-by":"publisher","first-page":"5355","DOI":"10.1103\/PhysRevE.58.5355","volume":"58","author":"T Kadowaki","year":"1998","unstructured":"Kadowaki, T., Nishimori, H.: Quantum annealing in the transverse Ising model. Phys. Rev. E 58, 5355\u20135363 (1998). https:\/\/doi.org\/10.1103\/PhysRevE.58.5355","journal-title":"Phys. Rev. E"},{"key":"4025_CR25","doi-asserted-by":"crossref","unstructured":"Gily\u00e9n, A., Su, Y., Low, G.H., Wiebe, N.: Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pp. 193\u2013204 (2019)","DOI":"10.1145\/3313276.3316366"},{"key":"4025_CR26","doi-asserted-by":"publisher","unstructured":"Camps, D., Beeumen, R.V.: Fable: Fast approximate quantum circuits for block-encodings. In: 2022 IEEE International Conference on Quantum Computing and Engineering (QCE), pp. 104\u2013113 (2022). https:\/\/doi.org\/10.1109\/QCE53715.2022.00029","DOI":"10.1109\/QCE53715.2022.00029"},{"key":"4025_CR27","volume-title":"Quantum Computation and Quantum Information","author":"MA Nielsen","year":"2010","unstructured":"Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information, 10th edn. Cambridge University Press, Cambridge (2010)","edition":"10"},{"issue":"3","key":"4025_CR28","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.98.032309","volume":"98","author":"K Mitarai","year":"2018","unstructured":"Mitarai, K., Negoro, M., Kitagawa, M., Fujii, K.: Quantum circuit learning. Phys. Rev. A 98(3), 032309 (2018)","journal-title":"Phys. Rev. A"},{"issue":"4","key":"4025_CR29","first-page":"482","volume":"19","author":"JC Spall","year":"1998","unstructured":"Spall, J.C.: An overview of the simultaneous perturbation method for efficient optimization. Johns Hopkins APL Tech. Digest 19(4), 482\u2013492 (1998)","journal-title":"Johns Hopkins APL Tech. Digest"},{"key":"4025_CR30","doi-asserted-by":"crossref","unstructured":"Suzuki, Y., Yano, H., Raymond, R., Yamamoto, N.: Normalized gradient descent for variational quantum algorithms. In: 2021 IEEE International Conference on Quantum Computing and Engineering (QCE), pp. 1\u20139 (2021)","DOI":"10.1109\/QCE52317.2021.00015"},{"issue":"11","key":"4025_CR31","doi-asserted-by":"publisher","first-page":"4818","DOI":"10.1109\/TAC.2019.2914998","volume":"64","author":"R Murray","year":"2019","unstructured":"Murray, R., Swenson, B., Kar, S.: Revisiting normalized gradient descent: fast evasion of saddle points. IEEE Trans. Autom. Control 64(11), 4818\u20134824 (2019). https:\/\/doi.org\/10.1109\/TAC.2019.2914998","journal-title":"IEEE Trans. Autom. Control"},{"key":"4025_CR32","unstructured":"Hagberg, A., Swart, P., Chult, D.S.: Exploring network structure, dynamics, and function using networkX. Technical report, Los Alamos National Lab. (LANL), Los Alamos, NM (United States) (2008)"},{"key":"4025_CR33","unstructured":"Cross, A.: The IBM Q experience and QISKit open-source quantum computing software. In: APS March Meeting Abstracts, vol. 2018, pp. 58\u2013003 (2018)"},{"key":"4025_CR34","unstructured":"D-Wave Systems: D-Wave Leap. https:\/\/www.dwavesys.com\/take-leap (2021)"},{"key":"4025_CR35","unstructured":"D-Wave Systems: D-Wave Ocean Software Documentation. https:\/\/docs.ocean.dwavesys.com\/ (2021)"},{"issue":"7","key":"4025_CR36","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s11128-020-02692-8","volume":"19","author":"M Willsch","year":"2020","unstructured":"Willsch, M., Willsch, D., Jin, F., De Raedt, H., Michielsen, K.: Benchmarking the quantum approximate optimization algorithm. Quantum Inf. Process. 19(7), 1\u201324 (2020)","journal-title":"Quantum Inf. Process."},{"key":"4025_CR37","unstructured":"Kingma, D.P., Ba, J.: Adam: a method for stochastic optimization. arXiv preprint arXiv:1412.6980 (2014)"},{"key":"4025_CR38","doi-asserted-by":"crossref","unstructured":"Powell, M.J.D.: A direct search optimization method that models the objective and constraint functions by linear interpolation. In: Advances in Optimization and Numerical Analysis, pp. 51\u201367. Springer, Dordrecht (1994)","DOI":"10.1007\/978-94-015-8330-5_4"},{"issue":"3","key":"4025_CR39","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1038\/s41592-019-0686-2","volume":"17","author":"P Virtanen","year":"2020","unstructured":"Virtanen, P., Gommers, R., Oliphant, T.E., Haberland, M., Reddy, T., Cournapeau, D., Burovski, E., Peterson, P., Weckesser, W., Bright, J., et al.: Scipy 1.0: fundamental algorithms for scientific computing in python. Nat. Methods 17(3), 261\u2013272 (2020)","journal-title":"Nat. Methods"}],"container-title":["Quantum Information Processing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-023-04025-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11128-023-04025-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-023-04025-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,23]],"date-time":"2024-10-23T23:19:05Z","timestamp":1729725545000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11128-023-04025-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,11]]},"references-count":39,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2023,7]]}},"alternative-id":["4025"],"URL":"https:\/\/doi.org\/10.1007\/s11128-023-04025-x","relation":{},"ISSN":["1573-1332"],"issn-type":[{"type":"electronic","value":"1573-1332"}],"subject":[],"published":{"date-parts":[[2023,7,11]]},"assertion":[{"value":"15 March 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 June 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 July 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no financial or non-financial competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"279"}}