Structure-guided Quantum Computing

Quantum computing [1] is an emerging computational model that tries to utilize quantum mechanical effects. It still needs to be clarified when and why computations involving quantum effects are advantageous over classical algorithms. Since quantum computers are not yet available at scale, it is of immense importance to develop high-quality simulators to understand possible use cases of this technology for the European Space Agency. Currently, only noisy intermediate-scale quantum (NISQ) machines are available, which use some quantum effects but are sensitive to their environment (noisy) and susceptible to decoherence. Parts of this technology fall into the broader class of Ising machines. Various implementations of such machines are available today but still subject to size limitations.

Hybrid Approaches to Utilize Ising Machines

Many problems of great importance in operations research, formal verification, and artificial intelligence are NP-complete and, thus, deemed infeasible. A recent route in tackling such problems are hardware accelerators, which are specialized chips build to solve one particular optimization problem. An Ising machine or Ising processing unit (IPU) [3] is a piece of hardware cable of finding the ground state of an Ising model. A prominent incarnation of Ising machines are quantum annealers that try to find the ground state using quantum tunneling [2].

However, hardware accelerators of this kind have a fundamental drawback: They can only solve instances of a fixed size, that is, the number of variables they can handle is determined during the fabrication of the chip. The Advanced Concepts Team studies hybrid approaches in which a classical algorithm utilizes an IPU to solve subproblems of affordable size. To that end, the quadratic unconstrained binary optimization (QUBO) problem that underlies the Ising model is translated into a logic problem (MaxSAT) in a structure-preserving way. The first goal of this project is the development of a pipeline that partitions the resulting MaxSAT formula into a well-structured part and an unstructured rest. We then plan to guide the solution process along the well-structured part using dynamic programming while the unstructured parts of the formula are cast back into a QUBO and solved using an IPU.

Graphical and Structural Representations of Quantum Processes

Tensor networks are graphical representations of computations on high-dimensional arrays used to study many-body quantum systems [3]. Tree decompositions are structural representations of graphs to measure their similarity to trees. It is well-known that these concepts are tightly linked [4]. In particular, quantum computations can be expressed as tensor networks and simulated using tree decompositions.

In the second part of this project, we investigate whether recent advances in structural graph theory can be used to speed up computations involving tensor networks. In particular, we aim to develop faster simulators for quantum circuits using these techniques. In the opposite direction, we investigate the effect common assumptions and restrictions on quantum computations have on the structural properties of the underlying tensor network. New insights into these effects will help to understand when and why a quantum computer may (or may not) have an advantage over a classical computer.

Entangled Project

This project is accompanied by the application-driven project Advancing electronic structure simulations, a multifaceted exploration.

References

[1] Michael A. Nielsen and Isaac L. Chuang
Quantum Computation and Quantum Information
Cambridge (2011)

[2] Mark W. Johnson et al.
Quantum annealing with manufactured spins
Nature 473, 194–198 (2011)

[3] Naeimeh Mohseni, Peter L. McMahon, and Tim Byrnes
Ising machines as hardware solvers of combinatorial optimization problems
Nature Reviews Physics 4, pages 363–379 (2022)

[4] Igor L. Markov and Yaoyun Shi
Simulating Quantum Computation by Contracting Tensor Networks
SIAM Journal on Computing 38, pages 963-981 (2008)