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:1710.02111 · Physical Review A

Environment-assisted analog quantum search

Leonardo Novo, Shantanav Chakraborty, Masoud Mohseni, Yasser Omar

Published Aug 13, 2018• 15 citations
arXivHTMLPDF

Abstract

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 $\ensuremath{\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/(n{\ensuremath{\sigma}}^{2})$ 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.

DOI
10.1103/physreva.98.022316

Related papers

Accelerated adiabatic quantum search algorithm via pulse control in a non-Markovian environment

Feng-Hua Ren, Zhao-Ming Wang, Lian-Ao Wu

Adiabatic quantum computation requires that the system remains in its ground state. However, an adiabatic process often loses partly or entirely its quantumness, such as entanglement in its long runtime, due to the system-environment interactions. Here we put forward an effective quantum control technique to realize the adiabatic quantum search algorithm in a nonadiabatic regime and in the presence of environment. Using the non-Markovian quantum state diffusion equation approach, we numerically study the system dynamics characterized by the success probability. The results show that the probability increases with decreasing coupling strength and temperature. In particular, non-Markovianity from the environment can help to enhance the success probability. By choosing a suitable pulse intensity and period, a high success probability can be obtained in a short runtime for weak system-bath coupling, low temperature, and strong non-Markovian heat baths.

Physical Review A•Dec 4, 2020•18 citations

Analog nature of quantum adiabatic unstructured search

Mikhail Slutskii, Tameem Albash, Lev Barash +1 more

Abstract The quantum adiabatic unstructured search algorithm is one of only a handful of quantum adiabatic optimization algorithms to exhibit provable speedups over their classical counterparts. With no fault tolerance theorems to guarantee the resilience of such algorithms against errors, understanding the impact of imperfections on their performance is of both scientific and practical significance. We study the robustness of the algorithm against various types of imperfections: limited control over the interpolating schedule, Hamiltonian misspecification, and interactions with a thermal environment. We find that the unstructured search algorithm’s quadratic speedup is generally not robust to the presence of any one of the above non-idealities, and in some cases we find that it imposes unrealistic conditions on how the strength of these noise sources must scale to maintain the quadratic speedup.

arXiv:1904.04420•New Journal of Physics•Oct 28, 2019•30 citations

Stochastic learning control of adiabatic speedup in a non-Markovian open qutrit system

Yang-Yang Xie, Feng-Hua Ren, Run-Hong He +2 more

Precise and efficient control of quantum systems is essential to perform quantum information-processing tasks. In terms of adiabatic speedup via leakage elimination operator approach, for a closed system, the ideal pulse control conditions have been theoretically derived by P-Q partitioning technique. However, it is a challenge to design the corresponding control pulses for an open system, which requires noisy environments to be addressed. In this paper, we apply the stochastic search procedures to an open qutrit system and successfully obtain the optimal control pulses for significant adiabatic speedup. The calculation results show that these optimal pulses allow us to acquire higher fidelities than the ideal pulses. The improvement of fidelity is large for relatively strong system-bath coupling strength and high bath temperature. For certain coupling strength and bath temperature, the maximal improvement can be achieved for a critical characteristic frequency which represents the memory time of the environment. Our investigation indicates that the stochastic search procedures are powerful tools to design control pulses for combating the detrimental effects of the environment.

arXiv:2208.08261•Physical Review A•Dec 16, 2022•11 citations

Noise-tolerant quantum speedups in quantum annealing without fine tuning

Eliot Kapit, Vadim Oganesyan

Abstract Quantum annealing is a powerful alternative model of quantum computing, which can succeed in the presence of environmental noise even without error correction. However, despite great effort, no conclusive demonstration of a quantum speedup (relative to state of the art classical algorithms) has been shown for these systems, and rigorous theoretical proofs of a quantum advantage (such as the adiabatic formulation of Grover’s search problem) generally rely on exponential precision in at least some aspects of the system, an unphysical resource guaranteed to be scrambled by experimental uncertainties and random noise. In this work, we propose a new variant of quantum annealing, called RFQA, which can maintain a scalable quantum speedup in the face of noise and modest control precision. Specifically, we consider a modification of flux qubit-based quantum annealing which includes low-frequency oscillations in the directions of the transverse field terms as the system evolves. We show that this method produces a quantum speedup for finding ground states in the Grover problem and quantum random energy model, and thus should be widely applicable to other hard optimization problems which can be formulated as quantum spin glasses. Further, we explore three realistic noise channels and show that the speedup from RFQA is resilient to 1/f-like local potential fluctuations and local heating from interaction with a sufficiently low temperature bath. Another noise channel, bath-assisted quantum cooling transitions, actually accelerates the algorithm and may outweigh the negative effects of the others. We also detail how RFQA may be implemented experimentally with current technology.

arXiv:1710.11056•Quantum Science and Technology•Dec 22, 2020•7 citations

Quantum search in a non-Markovian environment

Sheikh Parvez Mandal

This MS thesis explores the effects and origins of a 'noise with memory' in the dynamics of an open quantum system. The system considered here is a multi-qubit register performing the Grover's quantum search algorithm. We show that a Markovian-correlated noise can enhance the efficiency of the algorithm over a time correlation-less noise. We also analytically find the set of necessary and sufficient conditions for the algorithm's success probability to remain invariant with respect to the number of noisy sites in the register and point out that these conditions hold irrespective of the presence of time-correlations in the noise. We then investigate the origins of the type of noise considered. In this regard, a 'collisional model' is constructed that exactly reproduces the noisy evolution of the open system. Non-Markovianity in the system's evolution is then assessed using two well-known measures and they are shown to be non-coincident. Our model is then slightly modified to accommodate an elementary thermal bath. There we show that increasing the bath's temperature increases information drainage from the system.

arXiv:2303.14121•Mar 23, 2023•0 citations

Practical Quantum Search by Variational Quantum Eigensolver on Noisy Intermediate-Scale Quantum Hardware

Chen-Yu Liu

Grover search is a renowned quantum search algorithm that leverages quantum superposition to find a marked item with quadratic speedup. However, when implemented on Noisy Intermediate-scale Quantum (NISQ) hardware, the required repeated iterations of the oracle and diffusion operators increase exponentially with the number of qubits, resulting in significant noise accumulation. To address this, we propose a hybrid quantum-classical architecture that replaces quantum iterations with updates from a classical optimizer. This optimizer minimizes the expectation value of an oracle Hamiltonian with respect to a parameterized quantum state representing the target bit string. Our parameterized quantum circuit is much shallower than Grover search circuit, and we found that it outperforms Grover search on noisy simulators and NISQ hardware. When the number of qubits is greater than 5, our approach still maintains usable success probability, while the success probability of Grover search is at the same level as random guessing.

arXiv:2304.03747•International Conference on Computational Science and Computational Intelligence (CSCI)•Dec 13, 2023•12 citations
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 nnn 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 \ensuremathσ\ensuremath{\sigma}\ensuremathσ, 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/(n\ensuremathσ2)1/(n{\ensuremath{\sigma}}^{2})1/(n\ensuremathσ2) to at least 1/21/21/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.
Adiabatic quantum computation requires that the system remains in its ground state. However, an adiabatic process often loses partly or entirely its quantumness, such as entanglement in its long runtime, due to the system-environment interactions. Here we put forward an effective quantum control technique to realize the adiabatic quantum search algorithm in a nonadiabatic regime and in the presence of environment. Using the non-Markovian quantum state diffusion equation approach, we numerically study the system dynamics characterized by the success probability. The results show that the probability increases with decreasing coupling strength and temperature. In particular, non-Markovianity from the environment can help to enhance the success probability. By choosing a suitable pulse intensity and period, a high success probability can be obtained in a short runtime for weak system-bath coupling, low temperature, and strong non-Markovian heat baths.
Abstract The quantum adiabatic unstructured search algorithm is one of only a handful of quantum adiabatic optimization algorithms to exhibit provable speedups over their classical counterparts. With no fault tolerance theorems to guarantee the resilience of such algorithms against errors, understanding the impact of imperfections on their performance is of both scientific and practical significance. We study the robustness of the algorithm against various types of imperfections: limited control over the interpolating schedule, Hamiltonian misspecification, and interactions with a thermal environment. We find that the unstructured search algorithm’s quadratic speedup is generally not robust to the presence of any one of the above non-idealities, and in some cases we find that it imposes unrealistic conditions on how the strength of these noise sources must scale to maintain the quadratic speedup.
Precise and efficient control of quantum systems is essential to perform quantum information-processing tasks. In terms of adiabatic speedup via leakage elimination operator approach, for a closed system, the ideal pulse control conditions have been theoretically derived by P-Q partitioning technique. However, it is a challenge to design the corresponding control pulses for an open system, which requires noisy environments to be addressed. In this paper, we apply the stochastic search procedures to an open qutrit system and successfully obtain the optimal control pulses for significant adiabatic speedup. The calculation results show that these optimal pulses allow us to acquire higher fidelities than the ideal pulses. The improvement of fidelity is large for relatively strong system-bath coupling strength and high bath temperature. For certain coupling strength and bath temperature, the maximal improvement can be achieved for a critical characteristic frequency which represents the memory time of the environment. Our investigation indicates that the stochastic search procedures are powerful tools to design control pulses for combating the detrimental effects of the environment.
Abstract Quantum annealing is a powerful alternative model of quantum computing, which can succeed in the presence of environmental noise even without error correction. However, despite great effort, no conclusive demonstration of a quantum speedup (relative to state of the art classical algorithms) has been shown for these systems, and rigorous theoretical proofs of a quantum advantage (such as the adiabatic formulation of Grover’s search problem) generally rely on exponential precision in at least some aspects of the system, an unphysical resource guaranteed to be scrambled by experimental uncertainties and random noise. In this work, we propose a new variant of quantum annealing, called RFQA, which can maintain a scalable quantum speedup in the face of noise and modest control precision. Specifically, we consider a modification of flux qubit-based quantum annealing which includes low-frequency oscillations in the directions of the transverse field terms as the system evolves. We show that this method produces a quantum speedup for finding ground states in the Grover problem and quantum random energy model, and thus should be widely applicable to other hard optimization problems which can be formulated as quantum spin glasses. Further, we explore three realistic noise channels and show that the speedup from RFQA is resilient to 1/f-like local potential fluctuations and local heating from interaction with a sufficiently low temperature bath. Another noise channel, bath-assisted quantum cooling transitions, actually accelerates the algorithm and may outweigh the negative effects of the others. We also detail how RFQA may be implemented experimentally with current technology.
This MS thesis explores the effects and origins of a 'noise with memory' in the dynamics of an open quantum system. The system considered here is a multi-qubit register performing the Grover's quantum search algorithm. We show that a Markovian-correlated noise can enhance the efficiency of the algorithm over a time correlation-less noise. We also analytically find the set of necessary and sufficient conditions for the algorithm's success probability to remain invariant with respect to the number of noisy sites in the register and point out that these conditions hold irrespective of the presence of time-correlations in the noise. We then investigate the origins of the type of noise considered. In this regard, a 'collisional model' is constructed that exactly reproduces the noisy evolution of the open system. Non-Markovianity in the system's evolution is then assessed using two well-known measures and they are shown to be non-coincident. Our model is then slightly modified to accommodate an elementary thermal bath. There we show that increasing the bath's temperature increases information drainage from the system.
Grover search is a renowned quantum search algorithm that leverages quantum superposition to find a marked item with quadratic speedup. However, when implemented on Noisy Intermediate-scale Quantum (NISQ) hardware, the required repeated iterations of the oracle and diffusion operators increase exponentially with the number of qubits, resulting in significant noise accumulation. To address this, we propose a hybrid quantum-classical architecture that replaces quantum iterations with updates from a classical optimizer. This optimizer minimizes the expectation value of an oracle Hamiltonian with respect to a parameterized quantum state representing the target bit string. Our parameterized quantum circuit is much shallower than Grover search circuit, and we found that it outperforms Grover search on noisy simulators and NISQ hardware. When the number of qubits is greater than 5, our approach still maintains usable success probability, while the success probability of Grover search is at the same level as random guessing.