Quantum computing & optimization
From quantum-inspired graph problems to fault-tolerant resource estimates.
My quantum-related research spans constrained perfect matching, higher-order Ising models, and quantum optimization. With Moshe Vardi, I developed Tutte-based hybrid SAT encodings for a matching problem motivated by quantum computing. In collaborative work on QAOA, we analyzed the resources and assumptions needed for a potential advantage over classical optimization.
Quantum-inspired graph problems
Some problems motivated by quantum computing can be expressed as constrained perfect matching in colored graphs. Our work uses Tutte’s theorem to build hybrid Boolean encodings that exploit the structure of the problem, rather than relying on a direct encoding alone. This is a classical constraint-solving approach to a quantum-inspired problem.
When could quantum optimization help?
In collaborative work, we studied fault-tolerant QAOA combined with amplitude amplification on random 8-SAT. The analysis compares quantum resource estimates with strong classical solvers, accounting for runtime, error correction, and energy assumptions. The conclusions concern modeled crossover conditions, rather than an experimental demonstration of quantum advantage.
Higher-order models
Related work on IsingSim develops a customizable framework for higher-order Ising simulation, including efficient differentiation of hyperedge functions.
Related papers
Perfect matching · IJCAI 2023 Vertex-color constraints Fault-tolerant quantum advantage Higher-order Ising HamiltoniansQuantum-Graph Best-Paper of 2023 · Max Planck Institute