Quantum Algorithms for Optimization ongoing

Computational devices and quantum mechanics revolutionized the 20th century. Quantum computation merges these fields to solve optimization problems faster than classical computers. This project aims to develop new quantum algorithms for general-purpose and specific applications, including optimization, mixed-integer programs, and uses in machine learning, logistics, big data, and physics. We will explore quantum dynamic programming, graph sparsification, and QAOA-type algorithms for small quantum computers.

🧑‍🎓 Project Members (excluding external)

Patrick Gelß
Principal Investigator
gelss (at) zib.de
Sebastian Pokutta
Principal Investigator
pokutta (at) zib.de

🪙 Funding

This project is being funded by the EU ERA-LEARN QuantERA II Call 2021 from May 2022 to April 2025.

🔬 Project Description

Computational devices and closely-related information-processing technologies are among the most revolutionary inventions of the past century. Another groundbreaking discovery of the 20th century was quantum mechanics. Developed as a theoretical model to describe physics at the atomic level, it fundamentally changed our understanding of the world around us. The field of quantum computation stems from both of them. Its main objective is to understand how quantum mechanics changes our understanding of computation, especially the division between feasible and infeasible problems. Recent developments in quantum algorithms indicates that various optimization problems can be solved much faster on a quantum computer. Optimization problems permeate our society, they are key for the efficient operation of industry, logistics, and for countless other tasks that are crucial to the functioning of our modern society. Also, optimization problems are notoriously hard, and solving many of them precisely is out of reach of the most powerful modern computers even for modestly-sized instances. The radical vision of this project is to push the use of quantum computers for optimization tasks much further, developing new quantum algorithms which go well beyond the capability of even the best classical computers we have today. We aim at both general-purpose algorithms that can be used for a large variety of applications as well as more application- focused algorithms. We consider both continuous and discrete optimization, quantum algorithms for mixed-integer programs, as well as applications for machine learning, logistics, big data and physics. Our approach includes recent and exciting developments like quantum dynamic programming and graph sparsification. We are also interested in studying the QAOA-type algorithms, which can be executed even on really small quantum computers like the ones available today. The QOPT project is aimed at producing quantum algorithms for a variety of different flavours of optimization problems and attains a significant impact on state-of-the-art of quantum algorithms in the following ways: identification of new opportunities and applications fostered through quantum technologies, enhancing interdisciplinarity and crossing traditional boundaries between disciplines in order to enlarge the community involved in tackling these new challenges, creating diverse and inclusive quantum community, and spreading excellence throughout Europe by involving partners from the widening countries.

💬 Talks and posters

Conference and workshop talks

Jul 2024
Bell and Grothendieck Meet Frank-Wolfe by Sébastien Designolle
25th International Symposium on Mathematical Programming (ISMP), Montréal
Feb 2024
Fredholm Integral Equations for the Training of Shallow Neural Networks by Patrick Gelß
7th SIAM conference on uncertainty quantification (SIAM UQ)
Sep 2023
Fredholm Integral Equations for the Training of Shallow Neural Networks by Patrick Gelß
7th ZIB-IMI-ISM-NUS-RIKEN-MODAL Workshop, Berlin
Jun 2023
Fredholm Integral Equations for the Training of Shallow Neural Networks by Patrick Gelß
workshop on quantum computation and optimization, Berlin
Jun 2023
Improved Local Models and New Bell Inequalities by Sébastien Designolle
workshop on quantum computation and optimization, Berlin
Mar 2023
Improved Local Models and New Bell Inequalities Via Frank-Wolfe Algorithms by Sébastien Designolle
15th annual meeting photonic devices, Berlin
Sep 2022
Low-rank Tensor Decompositions of Quantum Circuits by Patrick Gelß
6th ZIB-IMI-ISM-NUS-RIKEN-MODAL Workshop, Tokyo / Fukuoka
May 2022
Low-rank Tensor Decompositions of Quantum Circuits by Patrick Gelß
3rd workshop on quantum algorithms and applications, Brussels

Research seminar talks

Nov 2024
Bell and Grothendieck Meet Frank-Wolfe by Sébastien Designolle
ICFO seminar, Castelldefels
Nov 2024
Bell and Grothendieck Meet Frank-Wolfe by Sébastien Designolle
Valladolid seminar, Valladolid
Oct 2024
Bell and Grothendieck Meet Frank-Wolfe by Sébastien Designolle
quantum information & quantum computing working group seminar, Warsaw
Nov 2023
Frank-Wolfe Algorithms for Bell Nonlocality by Sébastien Designolle
IRIF seminar, Paris
Nov 2023
Frank-Wolfe Algorithms for Bell Nonlocality by Sébastien Designolle
QAT seminar, Paris
Nov 2023
Frank-Wolfe Algorithms for Bell Nonlocality by Sébastien Designolle
SIERRA seminar, Paris
Nov 2023
Frank-Wolfe Algorithms for Bell Nonlocality by Sébastien Designolle
PhiQus seminar, Palaiseau
Nov 2023
Frank-Wolfe Algorithms for Bell Nonlocality by Sébastien Designolle
LIP6 seminar, Paris
Oct 2023
Frank-Wolfe Algorithms for Bell Nonlocality by Sébastien Designolle
QINFO seminar, Lyon
Jul 2023
Fredholm Integral Equations for the Training of Shallow Neural Networks by Patrick Gelß
IBM NOIP seminar, Berlin
Jun 2023
Fredholm Integral Equations for the Training of Shallow Neural Networks by Patrick Gelß
DESY CQTA seminar, Zeuthen
Mar 2023
Improved Local Models and New Bell Inequalities Via Frank-Wolfe Algorithms by Sébastien Designolle
JQIT seminar, Krakow
Feb 2023
Improved Local Models and New Bell Inequalities Via Frank-Wolfe Algorithms by Sébastien Designolle
Atomki seminar, Debrecen
Feb 2023
Improved Local Models and New Bell Inequalities Via Frank-Wolfe Algorithms by Sébastien Designolle
IQOQI seminar, Vienna
Oct 2022
The Tensor-train Format and Its Applications by Patrick Gelß
Tensor Learning Team Seminar

📝 Publications and preprints

  1. Gelß, P., Issagali, A., and Kornhuber, R. (2024). Fredholm Integral Equations for Function Approximation and the Training of Neural Networks. SIAM Journal on Mathematics of Data Science. DOI: 10.1137/23M156642X [URL] [arXiv]
    [BibTeX]
    @article{2023_GelssIssagaliKornhuber_Fredholmneuralnetworks,
      year = {2024},
      journal = {SIAM Journal on Mathematics of Data Science},
      doi = {10.1137/23M156642X},
      url = {https://epubs.siam.org/doi/abs/10.1137/23M156642X},
      archiveprefix = {arXiv},
      eprint = {2303.05262},
      primaryclass = {math.NA},
      author = {Gelß, Patrick and Issagali, Aizhan and Kornhuber, Ralf},
      title = {Fredholm Integral Equations for Function Approximation and the Training of Neural Networks}
    }
  2. Stengl, S.-M., Gelß, P., Klus, S., and Pokutta, S. (2024). Existence and Uniqueness of Solutions of the Koopman–von Neumann Equation on Bounded Domains. Journal of Physics A: Mathematical and Theoretical. DOI: 10.1088/1751-8121/ad6f7d [URL] [arXiv]
    [BibTeX]
    @article{2023_StenglGelssKlusPokutta_Koopmanvonneumann,
      year = {2024},
      journal = {Journal of Physics A: Mathematical and Theoretical},
      doi = {10.1088/1751-8121/ad6f7d},
      url = {https://iopscience.iop.org/article/10.1088/1751-8121/ad6f7d},
      archiveprefix = {arXiv},
      eprint = {2306.13504},
      primaryclass = {math.AP},
      author = {Stengl, Steven-Marian and Gelß, Patrick and Klus, Stefan and Pokutta, Sebastian},
      title = {Existence and Uniqueness of Solutions of the Koopman--von Neumann Equation on Bounded Domains}
    }
  3. Stengl, S.-M. (2024). An Alternative Formulation of the Quantum Phase Estimation Using Projection-based Tensor Decompositions. Quantum Information Processing, 23. DOI: 10.1007/s11128-024-04347-4 [URL] [arXiv]
    [BibTeX]
    @article{2023_Stengl_Quantumphaseestimation,
      year = {2024},
      journal = {Quantum Information Processing},
      volume = {23},
      doi = {10.1007/s11128-024-04347-4},
      url = {https://link.springer.com/article/10.1007/s11128-024-04347-4},
      archiveprefix = {arXiv},
      eprint = {2303.05894},
      primaryclass = {quant-ph},
      author = {Stengl, Steven-Marian},
      title = {An Alternative Formulation of the Quantum Phase Estimation Using Projection-based Tensor Decompositions}
    }
  4. Designolle, S., Iommazzo, G., Besançon, M., Knebel, S., Gelß, P., and Pokutta, S. (2023). Improved Local Models and New Bell Inequalities Via Frank-Wolfe Algorithms. Physical Review Research, 5(4). DOI: 10.1103/PhysRevResearch.5.043059 [arXiv] [slides] [code]
    [BibTeX]
    @article{2023_DesignolleEtAl_LocalmodelsBellinequalities,
      year = {2023},
      journal = {Physical Review Research},
      month = oct,
      volume = {5},
      number = {4},
      doi = {10.1103/PhysRevResearch.5.043059},
      archiveprefix = {arXiv},
      eprint = {2302.04721},
      primaryclass = {quant-ph},
      author = {Designolle, Sébastien and Iommazzo, Gabriele and Besançon, Mathieu and Knebel, Sebastian and Gelß, Patrick and Pokutta, Sebastian},
      title = {Improved Local Models and New Bell Inequalities Via Frank-Wolfe Algorithms},
      code = {https://github.com/ZIB-IOL/BellPolytopes.jl},
      slides = {https://www.pokutta.com/slides/20230808-tokyo-bell.pdf}
    }
  5. Gelß, P., Klein, R., Matera, S., and Schmidt, B. (2023). Quantum Dynamics of Coupled Excitons and Phonons in Chain-like Systems: Tensor Train Approaches and Higher-order Propagators. [arXiv]
    [BibTeX]
    @misc{2023_GelssKleinMateraSchmidt_QuantumdynamicsTensortrain,
      archiveprefix = {arXiv},
      eprint = {2302.03568},
      primaryclass = {quant-ph},
      year = {2023},
      author = {Gelß, Patrick and Klein, Rupert and Matera, Sebastian and Schmidt, Burkhard},
      title = {Quantum Dynamics of Coupled Excitons and Phonons in Chain-like Systems: Tensor Train Approaches and Higher-order Propagators}
    }
  6. Klus, S., and Gelß, P. (2023). Continuous Optimization Methods for the Graph Isomorphism Problem. [arXiv]
    [BibTeX]
    @misc{2023_KlusGelss_Continuousgraphisomorphism,
      archiveprefix = {arXiv},
      eprint = {2311.16912},
      primaryclass = {cs.DM},
      year = {2023},
      author = {Klus, Stefan and Gelß, Patrick},
      title = {Continuous Optimization Methods for the Graph Isomorphism Problem}
    }
  7. Riedel, J., Gelß, P., Klein, R., and Schmidt, B. (2023). WaveTrain: A Python Package for Numerical Quantum Mechanics of Chain-like Systems Based on Tensor Trains. The Journal of Chemical Physics, 158(16), 164801. DOI: 10.1063/5.0147314 [URL] [arXiv]
    [BibTeX]
    @article{2023_RiedelGelssKleinSchmidt_Wavetrain,
      year = {2023},
      journal = {The Journal of Chemical Physics},
      volume = {158},
      number = {16},
      pages = {164801},
      doi = {10.1063/5.0147314},
      url = {https://pubs.aip.org/aip/jcp/article/158/16/164801/2887212/WaveTrain-A-Python-package-for-numerical-quantum},
      archiveprefix = {arXiv},
      eprint = {2302.03725},
      primaryclass = {quant-ph},
      author = {Riedel, Jerome and Gelß, Patrick and Klein, Rupert and Schmidt, Burkhard},
      title = {WaveTrain: A Python Package for Numerical Quantum Mechanics of Chain-like Systems Based on Tensor Trains}
    }
  8. Gelß, P., Klein, R., Matera, S., and Schmidt, B. (2022). Solving the Time-independent Schrödinger Equation for Chains of Coupled Excitons and Phonons Using Tensor Trains. The Journal of Chemical Physics, 156, 024109. DOI: 10.1063/5.0074948 [URL] [arXiv]
    [BibTeX]
    @article{2021_GelssKleinMateraSchmidt_Tensortrainschrdinger,
      year = {2022},
      journal = {The Journal of Chemical Physics},
      volume = {156},
      pages = {024109},
      doi = {10.1063/5.0074948},
      url = {https://pubs.aip.org/aip/jcp/article/156/2/024109/2839835/Solving-the-time-independent-Schrodinger-equation},
      archiveprefix = {arXiv},
      eprint = {2109.15104},
      primaryclass = {physics.comp-ph},
      author = {Gelß, Patrick and Klein, Rupert and Matera, Sebastian and Schmidt, Burkhard},
      title = {Solving the Time-independent Schrödinger Equation for Chains of Coupled Excitons and Phonons Using Tensor Trains}
    }
  9. Gelß, P., Klus, S., Knebel, S., Shakibaei, Z., and Pokutta, S. (2022). Low-rank Tensor Decompositions of Quantum Circuits. [arXiv]
    [BibTeX]
    @misc{2022_GelssKlusShakibaeiPokutta_Lowranktensordecompositions,
      archiveprefix = {arXiv},
      eprint = {2205.09882},
      primaryclass = {quant-ph},
      year = {2022},
      author = {Gelß, Patrick and Klus, Stefan and Knebel, Sebastian and Shakibaei, Zarin and Pokutta, Sebastian},
      title = {Low-rank Tensor Decompositions of Quantum Circuits}
    }