Environment-assisted analog quantum search

Two main obstacles for observing quantum advantage in noisy intermediate-scale quantum computers (NISQ) are the finite-precision effects due to control errors, or disorders, and decoherence effects due to thermal fluctuations. It has been shown that dissipative quantum computation is possible in the presence of an idealized fully engineered bath. However, it is not clear, in general, what performance can be achieved by NISQ when internal bath degrees of freedom are not controllable. In this work, we consider the task of quantum search of a marked node on a complete graph of $n$ nodes in the presence of both static disorder and nonzero coupling to an environment. We show that, given fixed and finite levels of disorder and thermal fluctuations, there is an optimal range of bath temperatures that can significantly improve the success probability of the algorithm. Remarkably for a fixed disorder strength $\sigma$, the system relaxation time decreases for higher temperatures within a robust range of parameters. In particular, we demonstrate that for strong disorder, the presence of a thermal bath increases the success probability from $1/\left(n{\sigma }^2\right)$ to at least $1/2$. While the asymptotic running time is approximately maintained, the need to repeat the algorithm many times and issues associated with unitary over-rotations can be avoided as the system relaxes to an absorbing steady state. Furthermore, we discuss for what regimes of disorder and bath parameters quantum speedup is possible and mention conditions for which similar phenomena can be observed in more general families of graphs. Our work highlights that in the presence of static disorder, even nonengineered environmental interactions can be beneficial for a quantum algorithm.

Figure 1

Population at the solution node versus time for a complete graph of ${10}^6$ nodes where each node of the graph is affected by disorder of maximum strength $\sigma =0.007$ for the cases of no bath (oscillatory thin blue curve), thermal bath at inverse temperature $\beta =40$ (thick red curve), and at $\beta =15$ (dashed green curve). We find that the population at the solution is always low in the unitary regime implying that the algorithm needs to be repeated several times. In the case where the disordered system is coupled to a thermal bath, we consider that the bath has an Ohmic spectral density with a cutoff frequency ${\omega }_c=2$ and system-bath coupling $g=0.02$. We numerically solve the Bloch-Redfield master equation. The interaction with the thermal bath results in amplifying the population at the solution with time without compromising much in the algorithmic running time. Moreover, increasing the temperature of the bath ensures faster relaxation and improves the running time of the algorithm.

Figure 2

Comparison of population at the solution node with time for a complete graph of $100000$ nodes where each node of the graph is affected by weak diagonal disorder of standard deviation $\sigma =0.006$ in the unitary regime and in the presence of a thermal bath having a cutoff frequency of ${\omega }_c=2$ and system-bath coupling $g=0.04$. The oscillatory thin blue curve indicates the population in the unitary scenario, i.e., in the absence of a thermal bath. The thick red curve shows the population at the solution in the presence of a thermal bath at inverse temperature, $\beta =15$. The steady state of the thermal bath has an overlap of close to $1/2$ with the solution state.