Nicolas Kolbenschlag

Advisors

Dr.-Ing. Christopher Mutschler, Prof. Dr. Björn Eskofier

Duration

08 / 2023 – 02 / 2024

Abstract

Motivation

The rise of quantum computing has offered new opportunities to achieve computational tasks that classical computers cannot. However, to achieve quantum advantage over classical algorithms, it is necessary to design algorithms that can be executed on quantum hardware. Many of these algorithms require performing arithmetic operations, such as policy iteration in reinforcement learning.

However, quantum computers can only execute unitary operations, which means that matrix operations can only be performed with matrices that are unitaries. Unfortunately, not all matrices are unitaries, which presents a significant challenge in quantum computing. One option to address this issue is to use block-encodings to encode matrices into larger unitaries that then can be executed on quantum hardware. This approach allows us to reuse existing algorithms (or at least their main ideas) from the classical world in quantum computing, with the potential to speed up computations.

But the generation of block-encodings comes with a computational cost. When analyzing algorithms for  quantum advantage, this additional cost must be taken into account. While traditional approaches to generation of the required quantum circuits typically rely on a chosen heuristic, here we aim to explore machine-learning approaches, trading computational complexity for data availability.

 

Related Work

Until now, the existing literature does not provide the theoretical basis that is required to make easy use of block-encodings in reinforcement learning environments, let alone an implementation allowing for generation of appropriate quantum circuits for arbitrary environments. While a quantum algorithm for quantum policy iteration based on fast linear algebra with quantum computers was described [1], the quantum circuits required to realize block encodings for arithmetic operations have been hand-crafted for chosen toy environments. In order to leverage the full potential of block-encodings [2,3,4] for quantum-computing assisted reinforcement learning, the quantum circuit generation needs to be automated: For an input matrix or vector, an oracle-circuit for the corresponding block encoding needs to be output with as low a computational cost as possible. Automated generation procedures targeting block encodings have only recently received greater attention [5,6,7]. The proposed algorithms still feature unfavorable scaling in the problem dimension, calling for alternative approaches.

 

Objective

The main objective of the master thesis is to research approaches to the automated generation of quantum circuits for block-encoded matrices as they are required for the execution of the quantum policy iteration algorithm by Cherrat et al. [1]. The main outcomes will be a re-implementation of the quantum policy iteration algorithm and implementations for software tools capable of producing quantum circuits for block encodings as they are required for the quantum policy iteration algorithm for a given environment. From this objective, the following work packages have been derived.

References

[1] E. A. Cherrat et al., Quantum Reinforcement Learning via Policy Iteration, https://arxiv.org/abs/2203.01889

[2] S.Chakraborty et al., The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation, https://arxiv.org/abs/1804.01973

[3] A. Gilyen et al., Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics, https://dl.acm.org/doi/10.1145/3313276.3316366
[4] A.Gilyen et al., Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics, https://arxiv.org/abs/1806.01838

[5] D. Camps et al., Explicit Quantum Circuits for Block Encodings of Certain Sparse Matrices, https://arxiv.org/abs/2203.10236
[6] D. Camps et al., FABLE: Fast Approximate Quantum Circuits for Block-Encodings, https://arxiv.org/abs/2205.00081
[7] D. Camps et al., Approximate Quantum Circuit Synthesis using Block-Encodings, https://arxiv.org/abs/2007.01417
[8] L. Lin, Lecture Notes on Quantum Algorithms for Scientific Computation, https://arxiv.org/abs/2201.08309
[9] G.Brockman et al., Open AIGym, https://arxiv.org/abs/1606.01540

[10] A. Paler  et al., Machine Learning Optimization of Quantum Circuit Layouts, https://doi.org/10.1145/3565271
[11] I. Moflic et al., Graph Neural Network Autoencoders for Efficient Quantum Circuit Optimisation, https://arxiv.org/abs/2303.03280
[12] H. Fan et al., Optimizing quantum circuit placement via machine learning, https://dl.acm.org/doi/10.1145/3489517.3530403
[13] A. Vaswani et al., Attention Is All You Need, https://arxiv.org/abs/1706.03762
[14] S. Yun et al., Graph Transformer Networks, https://arxiv.org/abs/1911.06455