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.
Work packages
| WP | Description |
| WP1 | Linear-algebraic operations with block-encodingsAs a preparatory step for the implementation of the quantum policy iteration algorithm, a detailed understanding for the inner workings of block-encodings for the linear algebraic operations of multiplication, addition and inversion must be obtained. This requires both theoretical work, as well as practical implementations in a suitable SDK, such as IBM’s Quantum Information Science Kit (Qiskit). Using FABLE, quantum circuits can be generated to provide test cases to ensure the correctness of the performed implementations. |
| WP1.1 | Investigation of the Quantum Singular Value TransformThe realization of matrix inversion via block-encodings turns out to be more complicated than for the operations of matrix multiplication and addition. Here, the formalism of the Quantum Singular Value Transformation (QSVT) [8] will be employed in order to arrive at the required block-encoding of the inverse of a given matrix. To this end, an understanding of the abstract formalism behind the QSVT must be obtained. Further the elements of the abstract formalism have to be translated to appropriate quantum circuits. |
| WP1.2 | Implementation of matrix multiplication, addition and matrix inversion After obtaining an understanding of how to realize block encodings for each of the linear algebraic operations, including matrix inversion, implementations for the realization of the corresponding block encodings will be provided. While it is evident that FABLE can be employed for the generation of oracle quantum circuits as they are required for block encodings of matrix multiplication and addition, the potential use of FABLE for circuit generation in the context of the QSVT will be investigated. Existing software packages, e.g., for the optimization of the phase parameters of the so-called Quantum Signal Processing (QSP) operator entering QSVT will be integrated. The implementations will be tested for a range of matrix instances of varying size. |
| WP2 | Quantum policy iteration algorithmThis work package collects the tasks that are necessary in order to provide an implementation of the model-based quantum policy iteration algorithm a la Cherrat et al. [1]. Subroutines for the generation of block-encodings adapted to a given reinforcement learning environment will be provided. A particular class of reinforcement learning environments will be selected for testing the implementation in simulation. |
| WP2.1 | Implementation of the quantum policy iteration algorithm for a sandbox problemThe model-based version of the quantum policy iteration algorithm as proposed in ref. [1] will be implemented and tested. Leveraging the implementations of block-encoding based arithmetic operations, the policy evaluation step will be carried out with a quantum subroutine. The FABLE algorithm [6] can serve as a baseline for the generation of quantum circuits in order to realize block encodings for simple test environments. |
| WP2.2 | Testing and Convergence Study of the quantum policy iteration algorithmAfter implementing the algorithm, it can be executed. In this work package, a comparison between the convergence behavior of the classical policy iteration and the quantum version is made. The goal is to observe convergence of the quantum version of the algorithm in at most as many iterations of policy optimization as for the classical version. |
| WP3 | Investigation of quantum advantagesJust the fact that an algorithm is executed on a quantum computer does not necessarily mean that there has to be a quantum advantage. It would be interesting if the design and structure of this particular algorithm is suitable for leveraging quantum advantage and if there might be a method to generically derive “the amount of computation” in an algorithm that could not have been executed on classical hardware. (So the amount of entanglement for instance.) The objective will be fulfilled if a theoretical comparison of the quantum version of policy iteration and the classical version is delivered and the observations from the experimental setup match the expectations derived from theory. |
| WP3.1 | Investigation of possible quantum advantages in this and analysis of the computational cost of constructing block-encodings with FABLEIn this wokpackage the runtime complexity (in terms of quantum gates and classical operations) will be analyzed in greater detail. The results from the previous work package will be taken into account to verify whether the observations from the experiment agree with the expectations. If they do not agree, this work package includes pointing out the differences between both approaches and explaining where the unexpected behavior might come from. Furthermore, it is crucial to investigate whether the amount of computation which is required to construct the FABLE-circuits for the block-encodings is as large or larger than the computational cost saved in the form of quantum advantage. |
| WP4 | Block-encoding construction techniquesThe goal of this work package is to learn a machine learning model (classical or quantum) for the procedure of generating block-encodings from matrices. As mentioned above, the cost of constructing block-encodings could be a showstopper for its real world application if this initial cost evens the quantum advantage. That is why, it could be a promising research direction focusing on efficient techniques for constructing block-encodings.One approach might be to learn a machine learning model for this task. For this, a training dataset for matrices from a specific domain (matrices that occur in certain reinforcement learning environments, for instance) and a given block-encoding technique like FABLE will be needed. Afterwards, the mapping from matrix to block-encoding could be learned. The objective is considered as achieved when the question of whether the generation of block-encodings for arbitrary matrices or specific subset of matrices can be learned, can be answered. |
| WP4.1 | Literature review on generation of block-encodingsBefore diving deeper into a particular direction, an exhaustive literature review will be done. Further, after an initial literature review on alternative methods to automatically construct block encodings (besides FABLE), a suitable research direction will be selected. Promising directions are machine-learning based approaches that leverage the inherent graph structure of quantum circuits or so-called variational quantum compilation techniques. |
| WP4.2 | Implementation and experimentation for machine-learning based generation of block-encodingsThis work package will start with creating a dataset consisting of pairs of reinforcement learning environment-state matrices and its block-encodings that were collected during executing the quantum policy iteration algorithm as described above. Afterwards, one can try to fit a machine learning algorithm on the dataset. While synthesizing quantum circuits for arbitrary input unitaries seems to be a non-trivial task in the machine-learning setting [10,12], the task of constructing circuits for a given block encoding is believed to be much simpler due to its additional structure. A crucial aspect of the investigation will be how to encode knowledge about the problem structure in the machine-learning setting. Transformer [13,14] or graph-neural network [11] architectures lend themselves as promising models for the task at hand. |
| WP4.3 | Evaluation of methodsThe performance of such a model on a testset will provide a good first indicator for the feasibility of learning such mapping. After that, the goal is to replace FABLE in the implementation of quantum policy iteration from work package 2 with this new approach for generating block-encodings. The objective is considered as fulfilled (in case that learning such a model is possible) if the policy iteration algorithm still converges as before and the cost for generating block-encodings with the model is smaller than with FABLE. |
| WP5 | Theses and defenseThe findings from literature review and experimental results are laid down in the thesis in written form. Best practices will be incorporated and constraints from regulations will be followed. |
| WP5.1 | Thesis writingThe thesis includes foundational background knowledge, theoretical explanations, a description of the experimental setup as well as the results. |
| WP5.2 | Preparing for final presentation and thesis defenseBesides in the written theses, a summary of findings from the thesis is provided as a presentation. |
Schedule
Time schedule of work packages (WP):
| WP | Aug. 23 | Sep. 23 | Nov. 23 | Dec. 23 | Jan. 24 | Feb. 24 |
| WP1.2 | 50 | 30 | ||||
| WP1.2 | 50 | 20 | ||||
| WP2.1 | 50 | 60 | 20 | |||
| WP2.2 | 20 | 40 | ||||
| WP3.1 | 20 | 40 | ||||
| WP4.1 | 20 | 40 | ||||
| WP4.2 | 30 | 40 | 20 | |||
| WP4.3 | 30 | 30 | ||||
| WP5.1 | 40 | 60 | 90 | |||
| WP5.2 | 40 | 60 | ||||
| ∑ | 150 | 150 | 150 | 150 | 150 | 150 |
Workload in hours (total: 900 hours)
Literature
- E. A. Cherrat et al., Quantum Reinforcement Learning via Policy Iteration, https://arxiv.org/abs/2203.01889
- S. Chakraborty et al., The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation, https://arxiv.org/abs/1804.01973
- 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
- A. Gilyen et al., Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics, https://arxiv.org/abs/1806.01838
- D. Camps et al., Explicit Quantum Circuits for Block Encodings of Certain Sparse Matrices, https://arxiv.org/abs/2203.10236
- D. Camps et al., FABLE: Fast Approximate Quantum Circuits for Block-Encodings, https://arxiv.org/abs/2205.00081
- D. Camps et al., Approximate Quantum Circuit Synthesis using Block-Encodings, https://arxiv.org/abs/2007.01417
- L. Lin, Lecture Notes on Quantum Algorithms for Scientific Computation, https://arxiv.org/abs/2201.08309
- G. Brockman et al., Open AIGym, https://arxiv.org/abs/1606.01540
- A. Paler et al., Machine Learning Optimization of Quantum Circuit Layouts, https://doi.org/10.1145/3565271
- I. Moflic et al., Graph Neural Network Autoencoders for Efficient Quantum Circuit Optimisation, https://arxiv.org/abs/2303.03280
- H. Fan et al., Optimizing quantum circuit placement via machine learning, https://dl.acm.org/doi/10.1145/3489517.3530403
- A. Vaswani et al., Attention Is All You Need, https://arxiv.org/abs/1706.03762
- S. Yun et al., Graph Transformer Networks, https://arxiv.org/abs/1911.06455
