Abstract L0-regularization-based compressed sensing (L0-RBCS) has the potential to outperform L1-regularization-based compressed sensing (L1-RBCS), but the optimization in L0-RBCS is difficult because it is a combinatorial optimization problem. To perform optimization in L0-RBCS, we propose a quantum–classical hybrid system consisting of a quantum machine and a classical digital processor. The coherent Ising machine (CIM) is a suitable quantum machine for this system because this optimization problem can only be solved with a densely connected network. To evaluate the performance of the CIM-classical hybrid system theoretically, a truncated Wigner stochastic differential equation (W-SDE) is introduced as a model for the network of degenerate optical parametric oscillators, and macroscopic equations are derived by applying statistical mechanics to the W-SDE. We show that the system performance in principle approaches the theoretical limit of compressed sensing and this hybrid system may exceed the estimation accuracy of L1-RBCS in actual situations, such as in magnetic resonance imaging data analysis.
Addressing nonlinear numerical problems in quantum computing remains challenging, but several approaches, including Carleman linearization (CL), have been proposed to construct quantum algorithms for such problems. In this work, we develop a CL-based method for a high-dimensional nonlinear stochastic differential equation (SDE)
dXt=(A(t)Xt+F(t)Xt⊗s)dt+B(t)dWt for an
RN-valued random process
Xt, aiming at quantum speed-up with respect to the dimension
N. We introduce auxiliary processes
Ytj that approximate
Xt⊗j, derive a linearized system of SDEs for them, and obtain the linear ordinary differential equation (ODE) governing their expectations. We then apply a quantum ODE solver to it and, from the resulting quantum state, extract an estimate for the expectation of a linear function of
Xt by overlap estimation. We show that, provided the nonlinear and noise terms in the SDE are sufficiently small relative to the linear term, the CL error decreases exponentially with the truncation order
J in CL, and we can estimate the target expectation with a
polylog(N) number of queries to unitaries encoding coefficient matrices
A,
F, and
B. Finally, we also run a numerical demonstration for an SDE related to Langevin dynamics, observing the exponential decay of the CL error as
J increases.
We derive an adiabatic theory for a stochastic differential equation, $ \varepsilon\, \mathrm{d} X(s) = L_1(s) X(s)\, \mathrm{d} s + \sqrt{\varepsilon} L_2(s) X(s) \, \mathrm{d} B_s, $ under a condition that instantaneous stationary states of
L1(s) are also stationary states of
L2(s). We use our results to derive the full statistics of tunneling for a driven stochastic Schrödinger equation describing a dephasing process.