Optimal Control for Closed and Open System Quantum Optimization
- URL: http://arxiv.org/abs/2107.03517v1
- Date: Wed, 7 Jul 2021 22:57:57 GMT
- Title: Optimal Control for Closed and Open System Quantum Optimization
- Authors: Lorenzo Campos Venuti, Domenico D'Alessandro, Daniel A. Lidar
- Abstract summary: We provide a rigorous analysis of the quantum optimal control problem in the setting of a linear combination $s(t)B+ (1-s(t))C$ of two noncommuting Hamiltonians.
The target is to minimize the energy of the final problem'' Hamiltonian $C$, for a time-dependent and bounded control schedule.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We provide a rigorous analysis of the quantum optimal control problem in the
setting of a linear combination $s(t)B+(1-s(t))C$ of two noncommuting
Hamiltonians $B$ and $C$. This includes both quantum annealing (QA) and the
quantum approximate optimization algorithm (QAOA). The target is to minimize
the energy of the final ``problem'' Hamiltonian $C$, for a time-dependent and
bounded control schedule $s(t)\in [0,1]$ and $t\in \mc{I}:= [0,t_f]$. It was
recently shown, in a purely closed system setting, that the optimal solution to
this problem is a ``bang-anneal-bang'' schedule, with the bangs characterized
by $s(t)= 0$ and $s(t)= 1$ in finite subintervals of $\mc{I}$, in particular
$s(0)=0$ and $s(t_f)=1$, in contrast to the standard prescription $s(0)=1$ and
$s(t_f)=0$ of quantum annealing. Here we extend this result to the open system
setting, where the system is described by a density matrix rather than a pure
state. This is the natural setting for experimental realizations of QA and
QAOA. For finite-dimensional environments and without any approximations we
identify sufficient conditions ensuring that either the bang-anneal,
anneal-bang, or bang-anneal-bang schedules are optimal, and recover the
optimality of $s(0)=0$ and $s(t_f)=1$. However, for infinite-dimensional
environments and a system described by an adiabatic Redfield master equation we
do not recover the bang-type optimal solution. In fact we can only identify
conditions under which $s(t_f)=1$, and even this result is not recovered in the
fully Markovian limit. The analysis, which we carry out entirely within the
geometric framework of Pontryagin Maximum Principle, simplifies using the
density matrix formulation compared to the state vector formulation.
Related papers
- Quantum Error Suppression with Subgroup Stabilisation [3.4719087457636792]
Quantum state purification is the functionality that, given multiple copies of an unknown state, outputs a state with increased purity.
We propose an effective state purification gadget with a moderate quantum overhead by projecting $M$ noisy quantum inputs to their subspace.
Our method, applied in every short evolution over $M$ redundant copies of noisy states, can suppress both coherent and errors by a factor of $1/M$, respectively.
arXiv Detail & Related papers (2024-04-15T17:51:47Z) - The classical limit of Quantum Max-Cut [0.18416014644193066]
We show that the limit of large quantum spin $S$ should be understood as a semiclassical limit.
We present two families of classical approximation algorithms for $mathrmQMaxCut_S$ based on rounding the output of a semidefinite program to a product of Bloch coherent states.
arXiv Detail & Related papers (2024-01-23T18:53:34Z) - A quantum central path algorithm for linear optimization [5.450016817940232]
We propose a novel quantum algorithm for solving linear optimization problems by quantum-mechanical simulation of the central path.
This approach yields an algorithm for solving linear optimization problems involving $m$ constraints and $n$ variables to $varepsilon$-optimality.
In the standard gate model (i.e., without access to quantum RAM), our algorithm can obtain highly-precise solutions to LO problems using at most $$mathcalO left( sqrtm + n textsfnnz (A) fracR_1
arXiv Detail & Related papers (2023-11-07T13:26:20Z) - On Penalty Methods for Nonconvex Bilevel Optimization and First-Order
Stochastic Approximation [13.813242559935732]
We show first-order algorithms for solving Bilevel Optimization problems.
In particular, we show a strong connection between the penalty function and the hyper-objective.
We show an improved oracle-complexity of $O(epsilon-3)$ and $O(epsilon-5)$, respectively.
arXiv Detail & Related papers (2023-09-04T18:25:43Z) - A Quantum Approximation Scheme for k-Means [0.16317061277457]
We give a quantum approximation scheme for the classical $k$-means clustering problem in the QRAM model.
Our quantum algorithm runs in time $tildeO left( 2tildeO(frackvarepsilon) eta2 dright)$.
Unlike previous works on unsupervised learning, our quantum algorithm does not require quantum linear algebra subroutines.
arXiv Detail & Related papers (2023-08-16T06:46:37Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
We introduce two oblivious mirror descent algorithms based on a complementary composite setting.
Remarkably, both algorithms work without prior knowledge of the Lipschitz constant or smoothness of the objective function.
We show how to extend our framework to scale and demonstrate the efficiency and robustness of our methods on large scale semidefinite programs.
arXiv Detail & Related papers (2023-06-30T08:34:29Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems.
We show that the algorithm finds the optimal solution in time $O*(2(0.5-c)n)$ for an $n$-independent constant $c$.
We also show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case.
arXiv Detail & Related papers (2022-12-03T02:45:23Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
We investigate the problem of best identification in discounted linear Markov+Delta Decision in the fixed confidence setting under a generative model.
The lower bound as the solution of an intricate non- optimization program can be used as the starting point to devise such algorithms.
arXiv Detail & Related papers (2022-08-11T04:12:50Z) - Streaming Complexity of SVMs [110.63976030971106]
We study the space complexity of solving the bias-regularized SVM problem in the streaming model.
We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
arXiv Detail & Related papers (2020-07-07T17:10:00Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
We study the problem of finding a basis $S$ of $M$ such that $det(sum_i in Sv_i v_i v_itop)$ is maximized.
This problem appears in a diverse set of areas such as experimental design, fair allocation of goods, network design, and machine learning.
arXiv Detail & Related papers (2020-04-16T19:16:38Z) - Naive Exploration is Optimal for Online LQR [49.681825576239355]
We show that the optimal regret scales as $widetildeTheta(sqrtd_mathbfu2 d_mathbfx T)$, where $T$ is the number of time steps, $d_mathbfu$ is the dimension of the input space, and $d_mathbfx$ is the dimension of the system state.
Our lower bounds rule out the possibility of a $mathrmpoly(logT)$-regret algorithm, which had been
arXiv Detail & Related papers (2020-01-27T03:44:54Z)
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.