Data structures for quantum computing

Robert Wille, Professor at the Technical University of Munich and the Software Competence Center, discusses the key to data structures when solving quantum computing problems

Quantum computing solves some important problems that were beyond the reach of classical computers. However, developing applications for this new and upcoming technology has proven to be quite a challenge and requires effective tools. Data structures are essential in this respect: whenever someone seeks to simulate, compile, verify or debug a quantum algorithm, an efficient representation of, for example, quantum states or quantum operations is required. Considering that these representations often grow exponentially with respect to the number of qubits, this is not easy. In this article, we provide an overview of data structures for quantum computing available today.

Vectors and matrices

Vectors and matrices are the most intuitive data structure for quantum computing. They represent quantum states and quantum operations and can be realized directly in the memory of classical computers through 1 or 2 dimensional arrays.

This simple awareness, however, comes with a price: it always leads to an exponential amount of memory. This means that, even with huge supercomputing clusters, the maximum number of qubits that can be represented with them is around 50 – a huge limitation; especially given the large number of qubits that future quantum computers will work with.

Decision diagrams

Decision diagrams aim to overcome this exponential complexity by uncovering and exploiting redundancies in the quantum states and operations involved. The underlying vector or matrix is ​​represented as a graph with nodes and edges, where each node corresponds to a part of the vector/matrix.

Compaction comes from sharing: identical parts of a vector or matrix (or parts that, for example, differ only by a common subfactor) are represented by the same node. The efficiency of the compaction of decision diagrams is strongly dependent on the state or the quantum operation considered. While there are cases where decision diagrams offer little reduction, other cases reduce memory requirements from several terabytes to just a few megabytes.

Tensor networks

Tensor networks can help alleviate the complexity of representing quantum states and operations by exploiting redundancies in the topological structure of the quantum circuit – instead of vectors/matrices. To translate a quantum circuit into a network of tensors, each object, be it a state or an operation, is represented by a multidimensional array of complex numbers – a tensor. For a circuit, tensors are connected to other tensors depending on the underlying quantum circuit. Then, extracting useful information from such a tensor network usually requires pairwise combining of tensors into a single remaining tensor in a process called contraction. Determining an efficient way to contract a given tensor network is one of the main challenges, but can eventually lead to rather compact representations.

ZX-Calculation

The ZX calculus is a graphical notation for quantum circuits equipped with a powerful set of rewrite rules that allow schematic reasoning about quantum computing. A ZX diagram is made up of colored nodes (called spiders) that are connected by threads. An important concept for ZX diagrams is the single paradigm of connectivity issues, which expresses that two ZX diagrams are considered equal if one can be transformed into the other simply by bending wires.

Any quantum circuit can be interpreted as a ZX diagram. However, ZX diagrams are more general than quantum circuits and allow representations that do not have meaningful interpretations as quantum circuits. It is this flexibility of being able to break out of the formalism of quantum circuits that makes ZX calculus a good intermediate language when working with quantum circuits.

More interest?

Did the overview above make you crave the details? Then see the following article, which provides more information, explicit examples, and references for further reading: R. Wille, L. Burgholzer, S. Hillmich, T. Grurl, A. Ploier, and T. Peham . The basis of design tools for quantum computing: tables, decision diagrams, tensor networks and ZX-Calculus. Design Automation Conference (DAC) 2022

The data structures summarized above are widely used in the Munich Quantum Toolkit (MQT) – an open source software toolkit for quantum computing developed at the Technical University of Munich. These tools are available at https://github.com/cda-tum/.

Also, a web-based GUI presenting a lightweight visualization of decision diagrams for quantum circuit simulation and quantum circuit verification is available at https://www.cda.cit.tum.de/app/ddvis /.

Try it today!