Online Learning Quantum States with the Logarithmic Loss via VB-FTRL
- URL: http://arxiv.org/abs/2311.04237v1
- Date: Mon, 6 Nov 2023 15:45:33 GMT
- Title: Online Learning Quantum States with the Logarithmic Loss via VB-FTRL
- Authors: Wei-Fu Tseng and Kai-Chun Chen and Zi-Hong Xiao and Yen-Huan Li
- Abstract summary: Online learning quantum states with the logarithmic loss (LL-OLQS) is a classic open problem in the field of online learning for over three decades.
In this note, we generalize VB-FTRL for LL-OLQS. Let $d$ the dimension $T$ the number of rounds.
Each of the algorithm consists of a semidefinite program that can be implemented in time by, e.g. cutting-plane methods.
- Score: 2.059931105362387
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Online learning quantum states with the logarithmic loss (LL-OLQS) is a
quantum generalization of online portfolio selection, a classic open problem in
the field of online learning for over three decades. The problem also emerges
in designing randomized optimization algorithms for maximum-likelihood quantum
state tomography. Recently, Jezequel et al. (arXiv:2209.13932) proposed the
VB-FTRL algorithm, the first nearly regret-optimal algorithm for OPS with
moderate computational complexity. In this note, we generalize VB-FTRL for
LL-OLQS. Let $d$ denote the dimension and $T$ the number of rounds. The
generalized algorithm achieves a regret rate of $O ( d^2 \log ( d + T ) )$ for
LL-OLQS. Each iteration of the algorithm consists of solving a semidefinite
program that can be implemented in polynomial time by, e.g., cutting-plane
methods. For comparison, the best-known regret rate for LL-OLQS is currently $O
( d^2 \log T )$, achieved by the exponential weight method. However, there is
no explicit implementation available for the exponential weight method for
LL-OLQS. To facilitate the generalization, we introduce the notion of
VB-convexity. VB-convexity is a sufficient condition for the logarithmic
barrier associated with any function to be convex and is of independent
interest.
Related papers
- Quantum Algorithms for the Pathwise Lasso [1.8058773918890538]
We present a novel quantum high-dimensional linear regression algorithm based on the classical LARS (Least Angle Regression) pathwise algorithm.
Our quantum algorithm provides the full regularisation path as the penalty term varies, but quadratically faster per iteration under specific conditions.
We prove, via an approximate version of the KKT conditions and a duality gap, that the LARS algorithm is robust to errors.
arXiv Detail & Related papers (2023-12-21T18:57:54Z) - Non-Linear Transformations of Quantum Amplitudes: Exponential
Improvement, Generalization, and Applications [0.0]
Quantum algorithms manipulate the amplitudes of quantum states to find solutions to computational problems.
We present a framework for applying a general class of non-linear functions to the amplitudes of quantum states.
Our work provides an important and efficient building block with potentially numerous applications in areas such as optimization, state preparation, quantum chemistry, and machine learning.
arXiv Detail & Related papers (2023-09-18T14:57:21Z) - Efficient quantum linear solver algorithm with detailed running costs [0.0]
We introduce a quantum linear solver algorithm combining ideasdiabatic quantum computing with filtering techniques based on quantum signal processing.
Our protocol reduces the cost of quantum linear solvers over state-of-the-art close to an order of magnitude for early implementations.
arXiv Detail & Related papers (2023-05-19T00:07:32Z) - Provably Efficient Exploration in Quantum Reinforcement Learning with Logarithmic Worst-Case Regret [23.418957451727255]
We propose a novel UCRL-style algorithm for quantum reinforcement learning (RL)
We establish an $mathcalO(mathrmpoly(S, A, H, log T))$ worst-case regret for it, where $T$ is the number of episodes.
Specifically, we develop a quantum algorithm based on value target regression (VTR) for linear mixture MDPs with $d$-dimensional linear representation.
arXiv Detail & Related papers (2023-02-21T16:23:11Z) - Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
We consider learning in an adversarial Decision Process (MDP) where the loss functions can change arbitrarily over $K$ episodes.
This paper provides two algorithms that improve the regret to $tildemathcal O(K2/3)$ in the same setting.
arXiv Detail & Related papers (2023-01-30T14:37:21Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits.
Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit.
We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
arXiv Detail & Related papers (2022-06-30T03:15:23Z) - Resource Optimisation of Coherently Controlled Quantum Computations with
the PBS-calculus [55.2480439325792]
Coherent control of quantum computations can be used to improve some quantum protocols and algorithms.
We refine the PBS-calculus, a graphical language for coherent control inspired by quantum optics.
arXiv Detail & Related papers (2022-02-10T18:59:52Z) - AsySQN: Faster Vertical Federated Learning Algorithms with Better
Computation Resource Utilization [159.75564904944707]
We propose an asynchronous quasi-Newton (AsySQN) framework for vertical federated learning (VFL)
The proposed algorithms make descent steps scaled by approximate without calculating the inverse Hessian matrix explicitly.
We show that the adopted asynchronous computation can make better use of the computation resource.
arXiv Detail & Related papers (2021-09-26T07:56:10Z) - Higher-order Derivatives of Weighted Finite-state Machines [68.43084108204741]
This work examines the computation of higher-order derivatives with respect to the normalization constant for weighted finite-state machines.
We provide a general algorithm for evaluating derivatives of all orders, which has not been previously described in the literature.
Our algorithm is significantly faster than prior algorithms.
arXiv Detail & Related papers (2021-06-01T19:51:55Z) - On solving classes of positive-definite quantum linear systems with
quadratically improved runtime in the condition number [0.0]
We show that solving a Quantum Linear System entails a runtime linear in $kappa$ when $A$ is positive definite.
We present two new quantum algorithms featuring a quadratic speed-up in $kappa$.
arXiv Detail & Related papers (2021-01-28T08:41:21Z) - Sparsified Linear Programming for Zero-Sum Equilibrium Finding [89.30539368124025]
We present a totally different approach to the problem, which is competitive and often orders of magnitude better than the prior state of the art.
With experiments on poker endgames, we demonstrate, for the first time, that modern linear program solvers are competitive against even game-specific modern variants of CFR.
arXiv Detail & Related papers (2020-06-05T13:48:26Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.