CONFERENCEHQCC + QOPT Joint Workshop
PROGRAMME
TALKS
Tuesday, June 10
14:00-14:30
Sebastian Knebel "Koopman-von Neumann Mechanics" (ZIB)
The use of quantum computers in the simulation of dynamical systems promises many advantages. In order to achieve this objective, it is necessary to employ a unitary description of the dynamical system. One approach to this is the Koopman-von Neumann framework. However, adapting this framework for practical quantum computation requires special discretizations. This talk presents a novel approach to bridge this gap, enabling efficient quantum simulations of classical dynamical systems.
14:30 – 15:00
Benoît Dubus “New random compiler for Hamiltonians via Markov Chains” (ULB)
Based on: arXiv:2411.06485
Hamiltonian simulation is an important task in many quantum algorithms, for example in frameworks such as adiabatic quantum computation (AQC) or singular value transformation. In addition, the simulation of quantum systems is an important objective on its own. In many cases, the Hamil tonian can be decomposed as a linear combination of simpler terms; for instance, a sum of one- or two-qubit Hamiltonians for Ising models or a sum of time-independent Hamiltonians with time-dependent coefficients in AQC. In this paper we develop a random compiler, similar to the first order randomized Trotter, or qDRIFT [1], leading to a new framework that is at the same time quite simple to implement and analyze and rather versatile as it supports a large class of randomization schemes as well as time-dependent weights. We first present the model and derive its governing equations. We then define and analyze the simulation error for a sum of two Hamiltonians, and generalize it to a sum of Q Hamiltonians. We prove an estimate on the number of gates necessary for simulation.
15:00 – 15:30
Aleksandrs Belovs “Does your quantum subroutine err? Don't be upset, we have a solution” (LU)
Based on arXiv:2502.09249
Given an algorithm that outputs the correct answer with bounded error, it is sometimes desirable to reduce this error to some arbitrarily small. The usual method, for both quantum and randomized algorithms, is a procedure called majority voting, which incurs a multiplicative overhead of from calling the algorithm this many times. A recent paper introduced a model of quantum computation called transducers, and showed how to reduce the error of a transducer arbitrarily with only constant overhead, using a construction analogous to majority voting called purification. In this paper, we present a new highly simplified construction of a purifier, that can be understood as a weighted walk on a line similar to a random walk interpretation of majority voting. In addition to providing a new perspective that is easier to contrast with majority voting, our purifier has exponentially better space complexity than the previous one, and quadratically better dependence on the soundness-completeness gap of the algorithm being purified. Our new purifier has nearly optimal query complexity, even down to the constant, which matters when one composes quantum algorithms to super-constant depth.
16:00 – 16:30
Zoltan Zimboras "The revival of variational quantum algorithms" (Wigner RCP)
16:30 – 17:00
Zoltan Kolarovszki "A line search strategy for training CV variational quantum circuits" (Wigner RCP)
Wednesday, June 11
10:30 – 11:00
Simon Apers “Quantum Speedup for Sampling Random Spanning Trees” (IRIF)
Based on arXiv:2504.15603
We present quantum algorithm for sampling random spanning trees from a weighted graph in O~(\sqrt{mn}) time, where n and m denote the number of vertices and edges, respectively. Our algorithm has sublinear runtime for dense graphs and achieves a quantum speedup over the best-known classical algorithm, which runs in O~(m) time. The approach carefully combines, on one hand, a classical method based on ``large-step'' random walks for reduced mixing time and, on the other hand, quantum algorithmic techniques, including quantum graph sparsification and a sampling-without-replacement variant of Hamoudi's multiple-state preparation. We also establish a matching lower bound, proving the optimality of our algorithm up to polylogarithmic factors. These results highlight the potential of quantum computing in accelerating fundamental graph sampling problems.
10:30 – 11:00
Kayal Chandrima “Approximate degree composition for recursive functions” (IRIF)
Based on arXiv:2407.08385
Approximate degree is known to be a lower bound on the quantum query complexity. For a measure $M$, composition question asks if $M(f\circ g) = \Theta (M(f) M(g)$. Even though the composition question for most of the measures based on decision tree (how does for a measure $M$?) has been answered, the complete picture is missing for approximate degree.
In this talk we will focus on the composition question of approximate degree. We will discuss methods (like dual witness) which have been tried to prove composition. This will allow us to prove composition for some interesting classes of functions. Specifically, we will see the composition result when the inner or the outer function is a recursive composition itself.
This is a joint work with Sourav Chakraborty, Rajat Mittal Manaswi Paraashar and Nitin Saurabh.
11:30 – 12:00
Yasser Omar "The Energetics of Quantum Computation" (PQI) via zoom
12:00 – 12:30
André Chailloux “Quantum advantage from soft decoders” (INRIA) via zoom
Based on arXiv:2411.12553
In the last years, Regev's reduction has been used as a quantum algorithmic tool for providing a quantum advantage for variants of the decoding problem. Following this line of work, the authors of [JSW+24] have recently come up with a quantum algorithm called Decoded Quantum Interferometry that is able to solve in polynomial time several optimization problems. They study in particular the Optimal Polynomial Interpolation (OPI) problem, which can be seen as a decoding problem on Reed-Solomon codes. In this work, we provide strong improvements for some instantiations of the OPI problem. The most notable improvements are for the ISIS problem (originating from lattice-based cryptography) on Reed-Solomon codes but we also study different constraints for OPI. Our results provide natural and convincing decoding problems for which we believe to have a quantum advantage. Our proof techniques involve the use of a soft decoder for Reed-Solomon codes, namely the decoding algorithm from Koetter and Vardy [KV03]. In order to be able to use this decoder in the setting of Regev's reduction, we provide a novel generic reduction from a syndrome decoding problem to a coset sampling problem, providing a powerful and simple to use theorem, which generalizes previous work and is of independent interest. We also provide an extensive study of OPI using the Koetter and Vardy algorithm.
14:00 – 14:30
Frédéric Magniez “Quantum Communication Advantage for Leader Election and Agreement” (IRIF)
Based on arXiv:2502.07416
This work focuses on understanding the quantum message complexity of two central problems in distributed computing, namely, leader election and agreement in synchronous message-passing communication networks. We show that quantum communication gives an advantage for both problems by presenting quantum distributed algorithms that significantly outperform their respective classical counterparts under various network topologies. While prior works have studied and analyzed quantum distributed algorithms in the context of (improving) round complexity, a key conceptual contribution of our work is positing a framework to design and analyze the message complexity of quantum distributed algorithms. We present and show how quantum algorithmic techniques such as Grover search, quantum counting, and quantum walks can make distributed algorithms significantly message-efficient. In particular, our leader election protocol for diameter-2 networks uses quantum walks to achieve the improved message complexity. To the best of our knowledge, this is the first such application of quantum walks in distributed computing.
14:30 – 15:00
Debbie Lim “Quantum Algorithm for Sparse Online Learning with Truncated Gradient Descent” (LU)
Based on arXiv:2411.03925
Logistic regression, the Support Vector Machine (SVM), and least squares are well-studied methods in the statistical and computer science community, with various practical applications. High-dimensional data arriving on a real-time basis makes the design of online learning algorithms that produce sparse solutions essential. In this work, we develop a quantum sparse online learning algorithm for logistic regression, the SVM, and least squares. Given efficient quantum access to the inputs, we show that a quadratic speedup in the time complexity with respect to the dimension of the problem is achievable, while maintaining a regret of $O(1/\sqrt{T})$, where $T$ is the number of iterations.
15:00 – 15:30
Etienne Objois “Quantum speed-up for Linear Programming using adaptive sparsification” (IRIF)
Thursday, June 12
10:00 – 10:30
Joseph Cunningham “Unstructured adiabatic quantum optimization: Optimality with limitations” (ULB)
Based on arXiv:2411.05736
In the circuit model of quantum computing, amplitude amplification techniques can be used to find solutions to NP-hard problems defined on n-bits in time poly(n) 2^{n/2}. In this work, we investigate whether such general statements can be made for adiabatic quantum optimization, as provable results regarding its performance are mostly unknown. Although a lower bound of \Omega(2^{n/2}) has existed in such a setting for over a decade, a purely adiabatic algorithm with this running time has been absent. We show that adiabatic quantum optimization using an unstructured search approach results in a running time that matches this lower bound (up to a polylogarithmic factor) for a broad class of classical local spin Hamiltonians. For this, it is necessary to bound the spectral gap throughout the adiabatic evolution and compute beforehand the position of the avoided crossing with sufficient precision so as to adapt the adiabatic schedule accordingly. However, we show that the position of the avoided crossing is approximately given by a quantity that depends on the degeneracies and inverse gaps of the problem Hamiltonian and is NP-hard to compute even within a low additive precision. Furthermore, computing it exactly (or nearly exactly) is #P-hard. Our work indicates a possible limitation of adiabatic quantum optimization algorithms, leaving open the question of whether provable Grover-like speed-ups can be obtained for any optimization problem using this approach.
10:30 – 11:00
Marian Stengl "Optimization-Driven Quantum Circuit Decomposition" (ZIB)
In this work, we investigate an optimization-based approach to quantum circuit decomposition. Starting with a fixed layout of one- and two qubit gates to be used, we aim to find suitable unitary gates to minimize the error between the operator resulting from the circuit and a given target gate. This results in a nonlinear, nonconvex optimization problem over complex, matrix-valued arguments with equality constraints.
To solve this problem, we use a penalty approach in which the unitarity constraints are relaxed. This introduces a sequence of surrogate problems. Analyzing the problem, we show that the penalty functional can be rewritten as the difference of two convex functionals. Together with results from Toland duality, this allows the derivation of a multiconvex reformulation of the penalized problem. Using this, we propose a descent-based optimization algorithm to solve the problem.
11:30 – 12:00
Maximilian Kramer "Measurement-driven SAT solving on a quantum computer" (Freie Universität Berlin)
3-SAT is a central problem in both theoretical computer science and applied optimization. While the NP-hardness of 3-SAT rules out an exponential separation between quantum and classical algorithms, even a polynomial advantage holds potential for significant practical value. Building upon arXiv:1711.02687, we work on establishing rigorous run-time guarantees for a promising measurement-based quantum algorithm for 3-SAT. This algorithm diverges fundamentally from the two dominant paradigms for quantum 3-SAT solvers: the 'groverization' of classical algorithms, which is limited to quadratic speedups and is less hardware-friendly, and quantum annealing/QAOA, which lack rigorous performance guarantees. Our analysis introduces two complementary frameworks for proving convergence rates of measurement-based quantum algorithms—one leveraging the detectability lemma and the other grounded in the method of alternating projections— which we believe are of independent interest.
This is joint work in progress of Franz J. Schreiber and Maximilian J. Kramer together with Alexander Nietner and Jens Eisert.
12:00 – 12:30
Jevgēnijs Vihrovs “Quantum Search on Computation Trees” (LU)
Based on arXiv:2505.22405
We show a simple generalization of the quantum walk algorithm for search in backtracking trees by Montanaro (ToC 2018) to the case where vertices can have different times of computation. If a vertex v in the tree of depth D is computed in t_v steps from its parent, then we show that detection of a marked vertex requires O(sqrt{T D}) queries to the steps of the computing procedures, where T = \sum_v t_v^2. This framework provides an easy and convenient way to re-obtain a number of other quantum frameworks like variable time search, quantum divide & conquer and bomb query algorithms. The underlying algorithm is simple, explicitly constructed, and has low poly-logarithmic factors in the complexity.
As a corollary, this gives a quantum algorithm for variable time search with unknown times with optimal query complexity. This resolves the open question of the query complexity of variable time search, as the matching lower bound was recently shown by Ambainis, Kokainis and Vihrovs (TQC’23). As another result, we obtain an O(n) time algorithm for the geometric task of determining if any three lines among n given intersect at the same point, improving the O(n^{1+o(1)}) algorithm of Ambainis and Larka (TQC’20).
12:30 – 13:00
Daniel Szabo “Quantum property testing of sparse directed graphs” (IRIF)
Based on arXiv:2410.05001
We initiate the study of quantum property testing in sparse directed graphs, and more particularly in the unidirectional model, where the algorithm is allowed to query only the outgoing edges of a vertex.
In the classical unidirectional model the problem of testing k-star-freeness, and more generally k-source-subgraph-freeness, is almost maximally hard for large k. We prove that this problem has almost quadratic advantage in the quantum setting. Moreover, we prove that this advantage is nearly tight, by showing a quantum lower bound using the method of dual polynomials on an intermediate problem for a new, property testing version of the k-collision problem that was not studied before.
To illustrate that not all problems in graph property testing admit such a quantum speedup, we consider the problem of 3-colorability in the related undirected bounded-degree model, when graphs are now undirected. This problem is maximally hard to test classically, and we show that also quantumly it requires a linear number of queries.
PARTICIPANTS
Simon Apers (IRIF)
Andris Ambainis (LU)
Aleksandrs Belovs (LU)
Elie Bermot (IRIF)
Joseph Cunningham (ULB)
Csaba Czaban (Wigner RCP)
Arne Darras (ULB)
Benoît Dubus (ULB)
Jens Eisert (FU Berlin)
Patrick Gelß (ZIB)
Chandrima Kayal (IRIF)
Sebastian Knebel (ZIB)
Zoltan Kolarovszki (Wigner RCP)
Maximilian Kramer (FU Berlin)
Debbie Lim (LU)
Frédéric Magniez (IRIF)
Benjamin Mathieu-Bloise (IRIF)
Johannes Jakob Meyer (FU Berlin)
Étienne Objois (IRIF)
Sayantan Sen (National University of Singapore)
Juris Smotrovs (LU)
Marian Stengl (ZIB)
Daniel Szabo (IRIF)
Jevgēnijs Vihrovs (LU)
Abuzer Yakaryilmaz (LU)
Zoltan Zimboras (Wigner RCP)
Yuxin Zhang (Chinese Academy of Science)