Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1701.03268 · IEEE Conference on Decision and Control (CDC)

Relaxation of the EM algorithm via quantum annealing for Gaussian mixture models

Hideyuki Miyahara, Koji Tsumura, Yuki Sughiyama

Published Dec 1, 2016• 2 citations
arXivHTMLPDF

Abstract

We propose a modified expectation-maximization algorithm by introducing the concept of quantum annealing, which we call the deterministic quantum annealing expectation-maximization algorithm (DQAEM). The expectation-maximization algorithm (EM) is an established algorithm to compute maximum likelihood estimates and applied to many practical applications. However, it is known that EM heavily depends on initial values and its estimates are sometimes trapped by local optima. To solve such a problem, quantum annealing (QA) was proposed as a novel optimization approach motivated by quantum mechanics. By employing QA, we then formulate DQAEM and present a theorem that supports its stability. Finally, we demonstrate numerical simulations to confirm its efficiency.

DOI
10.1109/cdc.2016.7798981

Related papers

Deterministic quantum annealing expectation-maximization algorithm

Hideyuki Miyahara, Koji Tsumura, Yuki Sughiyama

Abstract Maximum likelihood estimation (MLE) is one of the most important methods in machine learning, and the expectation-maximization (EM) algorithm is often used to obtain maximum likelihood estimates. However, EM heavily depends on initial configurations and fails to find the global optimum. On the other hand, in the field of physics, quantum annealing (QA) was proposed as a novel optimization approach. Motivated by QA, we propose a quantum annealing extension of EM, which we call the deterministic quantum annealing expectation-maximization (DQAEM) algorithm. We also discuss its advantage in terms of the path integral formulation. Furthermore, by employing numerical simulations, we illustrate how DQAEM works in MLE and show that DQAEM moderate the problem of local optima in EM.

arXiv:1704.05822•Journal of Statistical Mechanics Theory and Experiment•Nov 1, 2017•9 citations

Relaxation of the EM algorithm via quantum annealing

Hideyuki Miyahara, Koji Tsumura

The EM algorithm is a novel numerical method to obtain maximum likelihood estimates and is often used for practical calculations. However, many of maximum likelihood estimation problems are nonconvex, and it is known that the EM algorithm fails to give the optimal estimates by being trapped by local optima. In order to deal with this difficulty, we propose a deterministic quantum annealing EM algorithm by introducing the mathematical mechanism of quantum fluctuations into the conventional EM algorithm because quantum fluctuations induce the tunnel effect and are expected to relax the difficulty of nonconvex optimization problems in the maximum likelihood estimation problems. We show a theorem that guarantees its convergence and give numerical experiments to verify its efficiency.

arXiv:1606.01484•Proceedings of the ... American Control Conference/Proceedings of the American Control Conference•Jul 1, 2016•1 citation

Quantum Expectation-Maximization for Gaussian Mixture Models

Iordanis Kerenidis, Alessandro Luongo, Anupam Prakash

The Expectation-Maximization (EM) algorithm is a fundamental tool in unsupervised machine learning. It is often used as an efficient way to solve Maximum Likelihood (ML) estimation problems, especially for models with latent variables. It is also the algorithm of choice to fit mixture models: generative models that represent unlabelled points originating from $k$ different processes, as samples from $k$ multivariate distributions. In this work we define and use a quantum version of EM to fit a Gaussian Mixture Model. Given quantum access to a dataset of $n$ vectors of dimension $d$, our algorithm has convergence and precision guarantees similar to the classical algorithm, but the runtime is only polylogarithmic in the number of elements in the training set, and is polynomial in other parameters - as the dimension of the feature space, and the number of components in the mixture. We generalize further the algorithm in two directions. First, we show how to fit any mixture model of probability distributions in the exponential family. Then, we show how to use this algorithm to compute the Maximum a Posteriori (MAP) estimate of a mixture model: the Bayesian approach to likelihood estimation problems. We discuss the performance of the algorithm on a dataset that is expected to be classified successfully by this algorithm, arguing that on those cases we can give strong guarantees on the runtime.

arXiv:1908.06657•Aug 19, 2019•19 citations

Quantum extension of variational Bayes inference

Hideyuki Miyahara, Yuki Sughiyama

Variational Bayes (VB) inference is one of the most important algorithms in machine learning and is widely used in engineering and industry. However, VB is known to suffer from the problem of local optima. In this paper, we generalize VB by using quantum mechanics and propose an algorithm, which we call quantum annealing variational Bayes (QAVB) inference. We then show that QAVB drastically improves the performance of VB in a clustering problem described by a Gaussian mixture model, which is essentially important from the viewpoint of optimization. Finally, we discuss an intuitive understanding of how QAVB works well.

arXiv:1712.04709•Physical Review A•Aug 29, 2018•11 citations

基于量子退火算法的复杂优化问题求解

Jincheng Zhang

This paper investigates the application of the Quantum Annealing (QA) algorithm to solve complex optimization problems. The core claim is that simulating a complex optimization problem's local search process through the QA's annealing process can effectively locate global optimal solutions. The mechanism involves mapping the solution space of an optimization problem onto the annealing path of QA, controlling the annealing rate and path to guide the solution towards the optimal point. This research leverages QA's inherent ability to mimic physical annealing, aiming to enhance optimization efficiency and accuracy. We present a framework for formulating and applying QA to various complex problems, highlighting its potential advantages over traditional optimization methods. This work contributes to the growing field of quantum computing by demonstrating a practical approach to tackling challenging optimization tasks. The results suggest that QA can be a viable alternative for achieving superior performance in specific optimization scenarios.

•Sep 6, 2026•0 citations

Quantum Annealing Algorithm Optimization and Application

Jincheng Zhang

Quantum annealing (QA) is a promising quantum computing paradigm for solving optimization problems. However, the performance of QA is often limited by issues such as slow convergence rates and sensitivity to parameter settings. This paper presents a novel optimization method designed to address these limitations. The approach introduces refined parameters and an adaptive strategy to enhance the algorithm's convergence speed and solution accuracy. We explore the application of this optimized QA method to complex problems, demonstrating its potential for improved performance. The core of the optimization lies in modifying the annealing schedule and incorporating a dynamic adjustment of the magnetic field strength, denoted as $H(t)$, where $t$ represents time. The objective function to be minimized is typically represented as $E[s]$, where $s$ is the state vector of the quantum annealer. We introduce a variance reduction technique, denoted as $\sigma(t)$, which is dynamically adjusted based on the error estimates of the current state. The overall optimization process can be summarized as: $\min_{s} E[s] \quad \text{subject to} \quad \frac{dS}{dt} = - \beta(t) E[s] - \gamma(t) H(t)s$ where $\beta(t)$ is the annealing rate and $\gamma(t)$ is the magnetic field strength. The adaptive strategy involves updating $\beta(t)$ and $\gamma(t)$ based on the error in the current solution, aiming to reduce the variance $\sigma(t)$ and improve the convergence. The theoretical analysis suggests that this approach can significantly reduce the computational cost and improve the solution quality compared to traditional QA methods. Furthermore, we investigate the impact of different parameter settings on the algorithm's performance, highlighting the importance of careful tuning for optimal results. The results demonstrate a notable improvement in solution quality and convergence speed across various benchmark problems.

•Sep 3, 2026•0 citations
We propose a modified expectation-maximization algorithm by introducing the concept of quantum annealing, which we call the deterministic quantum annealing expectation-maximization algorithm (DQAEM). The expectation-maximization algorithm (EM) is an established algorithm to compute maximum likelihood estimates and applied to many practical applications. However, it is known that EM heavily depends on initial values and its estimates are sometimes trapped by local optima. To solve such a problem, quantum annealing (QA) was proposed as a novel optimization approach motivated by quantum mechanics. By employing QA, we then formulate DQAEM and present a theorem that supports its stability. Finally, we demonstrate numerical simulations to confirm its efficiency.
Abstract Maximum likelihood estimation (MLE) is one of the most important methods in machine learning, and the expectation-maximization (EM) algorithm is often used to obtain maximum likelihood estimates. However, EM heavily depends on initial configurations and fails to find the global optimum. On the other hand, in the field of physics, quantum annealing (QA) was proposed as a novel optimization approach. Motivated by QA, we propose a quantum annealing extension of EM, which we call the deterministic quantum annealing expectation-maximization (DQAEM) algorithm. We also discuss its advantage in terms of the path integral formulation. Furthermore, by employing numerical simulations, we illustrate how DQAEM works in MLE and show that DQAEM moderate the problem of local optima in EM.
The EM algorithm is a novel numerical method to obtain maximum likelihood estimates and is often used for practical calculations. However, many of maximum likelihood estimation problems are nonconvex, and it is known that the EM algorithm fails to give the optimal estimates by being trapped by local optima. In order to deal with this difficulty, we propose a deterministic quantum annealing EM algorithm by introducing the mathematical mechanism of quantum fluctuations into the conventional EM algorithm because quantum fluctuations induce the tunnel effect and are expected to relax the difficulty of nonconvex optimization problems in the maximum likelihood estimation problems. We show a theorem that guarantees its convergence and give numerical experiments to verify its efficiency.
The Expectation-Maximization (EM) algorithm is a fundamental tool in unsupervised machine learning. It is often used as an efficient way to solve Maximum Likelihood (ML) estimation problems, especially for models with latent variables. It is also the algorithm of choice to fit mixture models: generative models that represent unlabelled points originating from kkk different processes, as samples from kkk multivariate distributions. In this work we define and use a quantum version of EM to fit a Gaussian Mixture Model. Given quantum access to a dataset of nnn vectors of dimension ddd, our algorithm has convergence and precision guarantees similar to the classical algorithm, but the runtime is only polylogarithmic in the number of elements in the training set, and is polynomial in other parameters - as the dimension of the feature space, and the number of components in the mixture. We generalize further the algorithm in two directions. First, we show how to fit any mixture model of probability distributions in the exponential family. Then, we show how to use this algorithm to compute the Maximum a Posteriori (MAP) estimate of a mixture model: the Bayesian approach to likelihood estimation problems. We discuss the performance of the algorithm on a dataset that is expected to be classified successfully by this algorithm, arguing that on those cases we can give strong guarantees on the runtime.
Variational Bayes (VB) inference is one of the most important algorithms in machine learning and is widely used in engineering and industry. However, VB is known to suffer from the problem of local optima. In this paper, we generalize VB by using quantum mechanics and propose an algorithm, which we call quantum annealing variational Bayes (QAVB) inference. We then show that QAVB drastically improves the performance of VB in a clustering problem described by a Gaussian mixture model, which is essentially important from the viewpoint of optimization. Finally, we discuss an intuitive understanding of how QAVB works well.
This paper investigates the application of the Quantum Annealing (QA) algorithm to solve complex optimization problems. The core claim is that simulating a complex optimization problem's local search process through the QA's annealing process can effectively locate global optimal solutions. The mechanism involves mapping the solution space of an optimization problem onto the annealing path of QA, controlling the annealing rate and path to guide the solution towards the optimal point. This research leverages QA's inherent ability to mimic physical annealing, aiming to enhance optimization efficiency and accuracy. We present a framework for formulating and applying QA to various complex problems, highlighting its potential advantages over traditional optimization methods. This work contributes to the growing field of quantum computing by demonstrating a practical approach to tackling challenging optimization tasks. The results suggest that QA can be a viable alternative for achieving superior performance in specific optimization scenarios.
Quantum annealing (QA) is a promising quantum computing paradigm for solving optimization problems. However, the performance of QA is often limited by issues such as slow convergence rates and sensitivity to parameter settings. This paper presents a novel optimization method designed to address these limitations. The approach introduces refined parameters and an adaptive strategy to enhance the algorithm's convergence speed and solution accuracy. We explore the application of this optimized QA method to complex problems, demonstrating its potential for improved performance. The core of the optimization lies in modifying the annealing schedule and incorporating a dynamic adjustment of the magnetic field strength, denoted as H(t)H(t)H(t), where ttt represents time. The objective function to be minimized is typically represented as E[s]E[s]E[s], where sss is the state vector of the quantum annealer. We introduce a variance reduction technique, denoted as σ(t)\sigma(t)σ(t), which is dynamically adjusted based on the error estimates of the current state. The overall optimization process can be summarized as: min⁡sE[s]subject todSdt=−β(t)E[s]−γ(t)H(t)s\min_{s} E[s] \quad \text{subject to} \quad \frac{dS}{dt} = - \beta(t) E[s] - \gamma(t) H(t)smins​E[s]subject todtdS​=−β(t)E[s]−γ(t)H(t)s where β(t)\beta(t)β(t) is the annealing rate and γ(t)\gamma(t)γ(t) is the magnetic field strength. The adaptive strategy involves updating β(t)\beta(t)β(t) and γ(t)\gamma(t)γ(t) based on the error in the current solution, aiming to reduce the variance σ(t)\sigma(t)σ(t) and improve the convergence. The theoretical analysis suggests that this approach can significantly reduce the computational cost and improve the solution quality compared to traditional QA methods. Furthermore, we investigate the impact of different parameter settings on the algorithm's performance, highlighting the importance of careful tuning for optimal results. The results demonstrate a notable improvement in solution quality and convergence speed across various benchmark problems.