Publications

An Empirical Comparison of Optimizers for Quantum Machine Learning with SPSA-based Gradients

Marco Wiedmann, Marc Hölle, Maniraman Periyasamy, Nico Meyer, Christian Ufrecht, Daniel Scherer, Axel Plinge, Christopher Mutschler 

IEEE Quantum Week 2023, Sep 17–22, 2023 in Bellevue, Washington 
Quantum Applications Track (QAPP) Best Paper – 2nd Place

QA have attracted a lot of attention from the quantum computing community for the last few years. Their hybrid quantum-classical nature with relatively shallow quantum circuits makes them a promising platform for demonstrating the capabilities of NISQ devices. Although the classical machine learning community focuses on gradient-based parameter optimization, finding near-exact gradients for VQC with the parameter-shift rule introduces a large sampling overhead. Therefore, gradient-free optimizers have gained popularity in quantum machine learning circles. Among the most promising candidates is the SPSA algorithm, due to its low computational cost and inherent noise resilience. We introduce a novel approach that uses the approximated gradient from SPSA in combination with state-of-the-art gradient-based classical optimizers. We demonstrate numerically that this outperforms both standard SPSA and the parameter-shift rule in terms of convergence rate and absolute error in simple regression tasks. The improvement of our novel approach over SPSA with stochastic gradient decent is even amplified when shot- and hardware-noise are taken into account. We also demonstrate that error mitigation does not significantly affect our results.

Workshop Summary: Quantum Machine Learning

Volker Tresp, Steffen Udluft, Daniel Hein, Werner Hauptmann, Martin Leib, Christopher Mutschler, Daniel D. Scherer, Wolfgang Mauerer

International Workshop on Quantum Machine Learning: From Foundations to Applications (QML@QCE) Sep 17, 2023, in Bellevue, Washington

Quantum computing (QC) has made significant progress in recent years, and scientists are exploring its applications across various fields, including quantum machine learning (QML). The workshop ‘Quantum Machine Learning: From Foundations to Applications’, part of the IEEE International Conference on Quantum Computing and Engineering 2023, aims to bring together researchers and industry practitioners from different disciplines to discuss the challenges and applications of QML.

Quantum Natural Policy Gradients: Towards Sample-Efficient Reinforcement Learning

Nico Meyer, Daniel D. Scherer, Axel Plinge, Christopher Mutschler and Michael J. Hartmann

International Workshop on Quantum Machine Learning: From Foundations to Applications (QML@QCE) Sep 17, 2023, in Bellevue, Washington

Reinforcement learning is a growing field in AI with a lot of potential. Intelligent behavior is learned  automatically through trial and error in interaction with the environment. However, this learning process is often costly. Using variational quantum circuits as function approximators can reduce this cost. To implement this, we propose the quantum natural policy gradient (QNPG) algorithm -- a second-order gradient-based routine that takes advantage of an efficient approximation of the quantum Fisher information matrix. We experimentally demonstrate that QNPG outperforms first-order based training on Contextual Bandits environments regarding convergence speed and stability and thereby reduces the sample complexity. Furthermore, we provide evidence for the practical feasibility of our approach by training on a 12-qubit hardware device.

Differentiable Quantum Architecture Search for Quantum Reinforcement Learning

Yize Sun, Yunpu Ma, Volker Tresp

International Workshop on Quantum Machine Learning: From Foundations to Applications (QML@QCE) Sep 17, 2023, in Bellevue, Washington

Differentiable quantum architecture search (DQAS) is a gradient-based framework to design quantum circuits automatically in the NISQ era. It was motivated by such as low fidelity of quantum hardware, low flexibility of circuit architecture, high circuit design cost, barren plateau (BP) problem, and periodicity of weights. People used it to address error mitigation, unitary decomposition, and quantum approximation optimization problems based on fixed datasets. Quantum reinforcement learning (QRL) is a part of quantum machine learning and often has various data. QRL usually uses a manually designed circuit. However, the pre-defined circuit needs more flexibility for different tasks, and the circuit design based on various datasets could become intractable in the case of a large circuit. The problem of whether DQAS can be applied to quantum deep Q-learning with various datasets is still open. The main target of this work is to discover the capability of DQAS to solve quantum deep Q-learning problems. We apply a gradientbased framework DQAS on reinforcement learning tasks and evaluate it in two different environments - cart pole and frozen lake. It contains input- and output weights, progressive search, and other new features. The experiments conclude that DQAS can design quantum circuits automatically and efficiently. The evaluation results show significant outperformance compared to the manually designed circuit. Furthermore, the performance of the automatically created circuit depends on whether the supercircuit learned well during the training process. This work is the first to show that gradient-based quantum architecture search is applicable to QRL tasks.

Quantum Optimisation of General Join Trees

Schönberger, Manuel and Trummer, Immanuel and Mauerer, Wolfgang

2023 International Workshop on Quantum Data Science and Management

Recent advances in the manufacture of quantum computers attract much attention over a wide range of fields, as early-stage quantum processing units (QPU) have become accessible. While contemporary quantum systems are very limited, mature QPUs are speculated to excel at optimisation problems. Their use is hence very attractive for the database domain, which features a broad range of complex optimisation problems with large solution spaces. Yet, the use of QPUs on database problems remains largely unexplored, prompting further evaluation of the aptitude of quantum systems in the database domain, starting with its most fundamental problems. In this paper, we address the long-standing join ordering problem, one of the most extensively researched database problems. Rather than solving arbitrary problems, the use of QPUs requires specific mathematical problem encodings. Such a formulation was recently proposed for the join ordering problem, allowing first small-scale queries to be optimised on quantum hardware. However, the existing problem encoding is a faithful transformation of a mixed integer linear programming (MILP) formulation for JO, and hence inherits all limitations of the MILP method. Most strikingly, the existing encoding only considers a solution space with left-deep join trees, which tend to yield larger costs than general, bushy join trees. In this paper, we hence propose a novel QUBO encoding for the join ordering problem. Rather than transforming existing formulations, we present a native encoding tailored to quantum systems, which allows quantum optimisation of general, bushy join trees. Thereby, we exhaust the full potential of QPUs for join order optimisation.

Ready to Leap (by Co-Design)? Join Order Optimisation on Quantum Hardware

Schönberger, Manuel and Scherzinger, Stefanie and Mauerer, Wolfgang

2023 ACM SIGMOD/PODS International Conference on Management of Data

The prospect of achieving computational speedups by exploiting quantum phenomena makes the use of quantum processing units (QPUs) attractive for many algorithmic database problems. Query optimisation, which concerns problems that typically need to explore large search spaces, seems like an ideal match for quantum algorithms. We present the first quantum implementation of join ordering, one of the most investigated and fundamental query optimisation problems, based on a reformulation to quadratic binary unconstrained optimisation problems. We empirically characterise our method on two state-of-the-art approaches (gate-based quantum computing and quantum annealing), and identify speed-ups compared to the best know classical join ordering approaches for input sizes conforming to current quantum annealers. Yet, we also confirm that limits of early-stage technology are quickly reached. Current QPUs are classified as noisy, intermediate scale quantum computers (NISQ), and are restricted by a variety of limitations that reduce their capabilities as compared to ideal future QPUs, which prevents us from scaling up problem dimensions and reaching practical utility. To overcome these challenges, our formulation accounts for specific QPU properties and limitations, and allows us to trade between achievable solution quality and problem size. In contrast to all prior work on quantum computing for query optimisation and database-related challenges, we go beyond currently available QPUs, and explicitly target the scalability limitations: Using insights gained from numerical simulations and our experimental analysis, we identify key criteria for co-designing QPUs to improve their usefulness for join ordering, and show how even relatively minor physical architectural improvements can result in substantial enhancements. Finally, we outline a path towards practical utility of custom-designed QPUs.

QNEAT: Natural Evolution of Variational Quantum Circuit Architecture

Alessandro Giovagnoli, Volker Tresp, Yunpu Ma, and Matthias Schubert. 2023. 

Companion Conference on Genetic and Evolutionary Computation (GECCO '23 Companion). Association for Computing Machinery, New York, NY, USA, 647–650. 

Quantum Machine Learning (QML) is a recent and rapidly evolving field where the theoretical framework and logic of quantum mechanics are employed to solve machine learning tasks. Various techniques with different levels of quantum-classical hybridization have been proposed. Here we focus on variational quantum circuits (VQC), which emerged as the most promising candidates for the quantum counterpart of neural networks in the noisy intermediate-scale quantum (NISQ) era. Although showing promising results, VQCs can be hard to train because of different issues, e.g., barren plateau, periodicity of the weights, or choice of architecture. This paper focuses on this last problem for finding optimal architectures of variational quantum circuits for various tasks. To address it, we propose a gradient-free algorithm inspired by natural evolution to optimize both the weights and the architecture of the VQC. In particular, we present a version of the well-known neuroevolution of augmenting topologies (NEAT) algorithm and adapt it to the case of variational quantum circuits. We refer to the proposed architecture search algorithm for VQC as QNEAT. We test the algorithm with different benchmark problems of classical fields of machine learning i.e. reinforcement learning and combinatorial optimization.

Applicability of Quantum Computing on Database Query Optimization

Schönberger, Manuel

2022 International Conference on Management of Data, Philadelphia, PA, USA

We evaluate the applicability of quantum computing on two fundamental query optimization problems, join order optimization and multi query optimization (MQO). We analyze the problem dimensions that can be solved on current gate-based quantum systems and quantum annealers, the two currently commercially available architectures.

First, we evaluate the use of gate-based systems on MQO, previously solved with quantum annealing. We show that, contrary to classical computing, a different architecture requires involved adaptations. We moreover propose a multi-step reformulation for join ordering problems to make them solvable on current quantum systems. Finally, we systematically evaluate our contributions for gate-based quantum systems and quantum annealers. Doing so, we identify the scope of current limitations, as well as the future potential of quantum computing technologies for database systems.

Uncovering Instabilities in Variational-Quantum Deep Q-Networks

Maja Franz, Lucas Wolf, Maniraman Periyasamy, Christian Ufrecht, Daniel D. Scherer, Axel Plinge, Christopher Mutschler, Wolfgang Mauerer

Deep Reinforcement Learning (RL) has considerably advanced over the past decade. At the same time, state-of-the-art RL algorithms require a large computational budget in terms of training time to converge. Recent work has started to approach this problem through the lens of quantum computing, which promises theoretical speed-ups for several traditionally hard tasks. In this work, we examine a class of hybrid quantum-classical RL algorithms that we collectively refer to as variational quantum deep Q-networks (VQ-DQN). We show that VQ-DQN approaches are subject to instabilities that cause the learned policy to diverge, study the extent to which this afflicts reproducibility of established results based on classical simulation, and perform systematic experiments to identify potential explanations for the observed instabilities. Additionally, and in contrast to most existing work on quantum reinforcement learning, we execute RL algorithms on an actual quantum processing unit (an IBM Quantum Device) and investigate differences in behavior between simulated and physical quantum systems that suffer from implementation deficiencies. Our experiments show that, contrary to opposite claims in the literature, it cannot be conclusively decided if known quantum approaches, even if simulated without physical imperfections, can provide an advantage as compared to classical approaches. Finally, we provide a robust, universal and well-tested implementation of VQ-DQN as a reproducible testbed for future experiments.

Quantum Policy Iteration via Amplitude Estimation and Grover Search -- Towards Quantum Advantage for Reinforcement Learning

Simon Wiedemann, Daniel Hein, Steffen Udluft, Christian Mendl

We present a full implementation and simulation of a novel quantum reinforcement learning (RL) method and mathematically prove a quantum advantage. Our approach shows in detail how to combine amplitude estimation and Grover search into a policy evaluation and improvement scheme. We first develop quantum policy evaluation (QPE) which is quadratically more efficient compared to an analogous classical Monte Carlo estimation and is based on a quantum mechanical realization of a finite Markov decision process (MDP). Building on QPE, we derive a quantum policy iteration that repeatedly improves an initial policy using Grover search until the optimum is reached. Finally, we present an implementation of our algorithm for a two-armed bandit MDP which we then simulate. The results confirm that QPE provides a quantum advantage in RL problems.

1-2-3 Reproducibility for Quantum Software Experiments

Wolfgang Mauerer, Stefanie Scherzinger

Various fields of science face a reproducibility crisis. For quantum software engineering as an emerging field, it is therefore imminent to focus on proper reproducibility engineering from the start. Yet the provision of reproduction packages is almost universally lacking. Actionable advice on how to build such packages is rare, particularly unfortunate in a field with many contributions from researchers with backgrounds outside computer science. In this article, we argue how to rectify this deficiency by proposing a 1-2-3~approach to reproducibility engineering for quantum software experiments: Using a meta-generation mechanism, we generate DOI-safe, long-term functioning and dependency-free reproduction packages. They are designed to satisfy the requirements of professional and learned societies solely on the basis of project-specific research artefacts (source code, measurement and configuration data), and require little temporal investment by researchers. Our scheme ascertains long-term traceability even when the quantum processor itself is no longer accessible. By drastically lowering the technical bar, we foster the proliferation of reproduction packages in quantum software experiments and ease the inclusion of non-CS researchers entering the field.

Peel | Pile? Cross-Framework Portability of Quantum Software

Manuel Schönberger, Maja Franz, Stefanie. Scherzinger, Wolfgang Mauerer

In recent years, various vendors have made quantum software frameworks available. Yet with vendor-specific frameworks, code portability seems at risk, especially in a field where hardware and software libraries have not yet reached a consolidated state, and even foundational aspects of the technologies are still in flux. Accordingly, the development of vendor-independent quantum programming languages and frameworks is often suggested. This follows the established architectural pattern of introducing additional levels of abstraction into software stacks, thereby piling on layers of abstraction. Yet software architecture also provides seemingly less abstract alternatives, namely to focus on hardware-specific formulations of problems that peel off unnecessary layers. In this article, we quantitatively and experimentally explore these strategic alternatives, and compare popular quantum frameworks from the software implementation perspective. We find that for several specific, yet generalisable problems, the mathematical formulation of the problem to be solved is not just sufficiently abstract and serves as precise description, but is likewise concrete enough to allow for deriving framework-specific implementations with little effort. Additionally, we argue, based on analysing dozens of existing quantum codes, that porting between frameworks is actually low-effort, since the quantum- and framework-specific portions are very manageable in terms of size, commonly in the order of mere hundreds of lines of code. Given the current state-of-the-art in quantum programming practice, this leads us to argue in favour of peeling off unnecessary abstraction levels.

Modelling and Solving Reinforcement Learning Problems on Quantum Computers

Simon Wiedemann

Master Thesis at the Technische Universität München 15.11.2021

In the thesis, a new approach to use Quantum Computing for Reinforcement Learning is developed. The procedure is analogous to policy iteration that is using policy evaluation and policy improvement. These are realized by the quantum subroutines of quantum phase estimation and Grover search.

To this end, we first describe a quantum MDP model and based on it develop a quantum policy iteration algorithm. Allowing quantum agent-environment interaction via the exchange of states, actions and rewards in superposition to reduce the (q)sample complexity of learning appears to be a promising way to obtain quantum advantage in RL.

An implementation for two rounds of two-armed bandit with discount.