Quantum Software Consortium

Day 2 (Wednesday 23 April) @ 13:30–15:00

Tim Coopmans (Delft University of Technology)

Simulating quantum circuits using classical reasoning

Simulating quantum circuits exactly is provably difficult with regular computers, but that should not stop us from identifying efficient subcases or finding methods which work well in practice. In this talk, I will show how one can perform quantum-circuit simulation using decision diagrams or weighted #SAT, two techniques from the well-developed branch of computer science called classical reasoning. In addition, we prove that our novel decision diagram asymptotically scales incomparably to other techniques such as a one-dimensional tensor decomposition (tensor trains).

Joon Hyung Lee (Leiden University)

Quantum Variants – From Satisfiability to Spin Glasses

In this talk, we discuss two quantum variants of well-known mathematical systems: quantum k-SAT, rooted in discrete random systems, and the quantum Sherrington-Kirkpatrick (QSK) model from spin-glass theory. A shared theme is the use of classical techniques to analyze these quantum problems, providing novel insights into their mathematical structure and behavior.

We first explore the k-QSAT problem, where satisfiability hinges on the geometric structure of random factor graphs, addressed using methods from algebra and analysis. We then shift focus to the QSK model, examining spin correlations and phase transitions under a transverse field through classical spin-glass approaches, such as the TAP equations.

This talk is based on a preprint, https://arxiv.org/abs/2404.18447 and an ongoing project.  

Yaroslav Herasymenko (CWI)

Quantum learning between the spin group orbit and the Hilbert space of n quantum bits

An interesting problem in quantum computing is to learn the state vector of n quantum bits, given a sample of the copies of this state. For a general state vector, the sample size and computational time required for such a learning procedure scales exponentially in n. However, for some sets of possible unknown states, this learning complexity can be brought down to poly(n). One such efficiently learnable class of state vectors, which is also important in physics, are the so-called matchgate states. Mathematically, they are defined as the orbit of the so-called spin group Spin(2n). In this talk, I would like to describe the computational learning theory we developed for the states produced by actions of Spin(2n) and a few elementary unitaries outside of the spin group. By increasing the number t of such non-Spin(2n) unitaries, one can interpolate between the matchgate states and the general state on quantum bits. We prove that it is possible to learn the resulting states with poly(n2^t) resources. Furthermore, it is unlikely that the exponential scaling in t could be improved. In particular, we show that a better scaling would invalidate a conjecture in post-quantum cryptography, which is commonly believed to be true. Finally, I will outline how our approach allows efficiently testing whether an entirely unknown state belongs to the class of states for which our learning algorithm works.

This talk is based on the work done in collaboration with Antonio Anna Mele (FU Berlin), which can be accessed at https://arxiv.org/abs/2402.18665.