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

Quantum search at low temperature in the singleavoided crossing model

Parth Patel

Published Jan 1, 2019• 0 citations
OpenAlex

Abstract

We begin with an n-qubit quantum search algorithm and formulate it in terms of quantum walk and adiabatic quantum computation. We then represent and transform the n-qubit search algorithm into a two-level system and hence the single avoided crossing model. We perform and present the analytical calculations and numerical simulations of the dynamics of quantum walk search algorithm and AQC search algorithm in a thermal bath. We use the master equations formulation to represent the open quantum system. We nd out that while generally the performance of algorithms worsen with increase in temperature and the system size, there are interesting features in quantum walk search where there is an optimal low temperature for the best performance for other specied parameters. Similarly for AQC search, the performance generally worsens with increase in temperature, but for specied parameter ranges, the system is more robust against temperature eects.

Related papers

Adiabatic Quantum Search in Open Systems

Dominik S. Wild, Sarang Gopalakrishnan, Michael Knap +2 more

Adiabatic quantum algorithms represent a promising approach to universal quantum computation. In isolated systems, a key limitation to such algorithms is the presence of avoided level crossings, where gaps become extremely small. In open quantum systems, the fundamental robustness of adiabatic algorithms remains unresolved. Here, we study the dynamics near an avoided level crossing associated with the adiabatic quantum search algorithm, when the system is coupled to a generic environment. At zero temperature, we find that the algorithm remains scalable provided the noise spectral density of the environment decays sufficiently fast at low frequencies. By contrast, higher order scattering processes render the algorithm inefficient at any finite temperature regardless of the spectral density, implying that no quantum speedup can be achieved. Extensions and implications for other adiabatic quantum algorithms will be discussed.

arXiv:1606.01898•Physical Review Letters•Oct 6, 2016•28 citations

Quantum search with hybrid adiabatic–quantum-walk algorithms and realistic noise

James G. Morley, Nicholas Chancellor, Sougato Bose +1 more

Computing using a continuous-time evolution, based on the natural interaction Hamiltonian of the quantum computer hardware, is a promising route to building useful quantum computers in the near term. Adiabatic quantum computing, quantum annealing, computation by a continuous-time quantum walk, and special purpose quantum simulators all use this strategy. In this work, we carry out a detailed examination of adiabatic and quantum-walk implementation of the quantum search algorithm, using the more physically realistic hypercube connectivity, rather than the complete graph, for our base Hamiltonian. We calculate optimal adiabatic schedules both analytically and numerically for the hypercube and then interpolate between adiabatic and quantum-walk searching, obtaining a family of hybrid algorithms. We show that all of these hybrid algorithms provide the quadratic quantum speedup when run with optimal parameter settings, which we determine and discuss in detail. We incorporate the effects of multiple runs of the same algorithm, noise applied to the qubits, and two types of problem misspecification, determining the optimal hybrid algorithm for each case. Our results reveal a rich structure of how these different computational mechanisms operate and should be balanced in different scenarios. For large systems with low noise and good control, a quantum walk is the best choice, while hybrid strategies can mitigate the effects of many shortcomings in hardware and problem misspecification.

arXiv:1709.00371•Physical Review A•Feb 28, 2019•49 citations

Quantum search algorithms on a regular lattice

Birgit Hein, Gregor Tanner

Quantum algorithms for searching for one or more marked items on a $d$-dimensional lattice provide an extension of Grover's search algorithm including a spatial component. We demonstrate that these lattice search algorithms can be viewed in terms of the level dynamics near an avoided crossing of a one-parameter family of quantum random walks. We give approximations for both the level splitting at the avoided crossing and the effectively two-dimensional subspace of the full Hilbert space spanning the level crossing. This makes it possible to give the leading order behavior for the search time and the localization probability in the limit of large lattice size including the leading order coefficients. For $d=2$ and $d=3$, these coefficients are calculated explicitly. Closed form expressions are given for higher dimensions.

arXiv:1005.3676•Physical Review A•Jul 23, 2010•37 citations

Decoherence in adiabatic quantum computation

Tameem Albash, Daniel A. Lidar

Recent experiments with increasingly larger numbers of qubits have sparked renewed interest in adiabatic quantum computation, and in particular quantum annealing. A central question that is repeatedly asked is whether quantum features of the evolution can survive over the long time scales used for quantum annealing relative to standard measures of the decoherence time. We reconsider the role of decoherence in adiabatic quantum computation and quantum annealing using the adiabatic quantum master-equation formalism. We restrict ourselves to the weak-coupling and singular-coupling limits, which correspond to decoherence in the energy eigenbasis and in the computational basis, respectively. We demonstrate that decoherence in the instantaneous energy eigenbasis does not necessarily detrimentally affect adiabatic quantum computation, and in particular that a short single-qubit ${T}_{2}$ time need not imply adverse consequences for the success of the quantum adiabatic algorithm. We further demonstrate that boundary cancellation methods, designed to improve the fidelity of adiabatic quantum computing in the closed-system setting, remain beneficial in the open-system setting. To address the high computational cost of master-equation simulations, we also demonstrate that a quantum Monte Carlo algorithm that explicitly accounts for a thermal bosonic bath can be used to interpolate between classical and quantum annealing. Our study highlights and clarifies the significantly different role played by decoherence in the adiabatic and circuit models of quantum computing.

arXiv:1503.08767•Physical Review A•Jun 17, 2015•147 citations

Effects of dissipation on an adiabatic quantum search algorithm

Inés de Vega, Mari Carmen Bañuls, Armando Pérez

According to recent studies (Amin et al 2008 Phys. Rev. Lett. 100 060503), the effect of a thermal bath may improve the performance of a quantum adiabatic search algorithm. In this paper, we compare the effects of such a thermal environment on the algorithm performance with those of a structured environment similar to the one encountered in systems coupled to an electromagnetic field that exists within a photonic crystal. Whereas for all the parameter regimes explored here, the algorithm performance is worsened by contact with a thermal environment, the picture appears to be different when one considers a structured environment. In this case we show that by tuning the environment parameters to certain regimes, the algorithm performance can actually be improved with respect to the closed system case. Additionally, the relevance of considering the dissipation rates as complex quantities is discussed in both cases. More specifically, we find that the imaginary part of the rates cannot be neglected with the usual argument that it simply amounts to an energy shift and in fact influences crucially the system dynamics.

arXiv:1006.0461•New Journal of Physics•Dec 8, 2010•24 citations

Quantum algorithm for the simulation of open-system dynamics and thermalization

Hong-Yi Su, Ying Li

The quantum open-system simulation is an important category of quantum simulation. By simulating the thermalization process at zero temperature, we can solve the ground-state problem of quantum systems. To realize the open-system evolution on the quantum computer, we need to encode the environment using qubits. However, usually the environment is much larger than the system, i.e., numerous qubits are required if the environment is directly encoded. In this paper, we propose a way to simulate open-system dynamics by reproducing reservoir correlation functions using a minimized Hilbert space. In this way, we only need a small number of qubits to represent the environment. To simulate the $n\mathrm{th}\ensuremath{-}\mathrm{order}$ expansion of the time-convolutionless master equation by reproducing up to $n$-time correlation functions, the number of qubits representing the environment is $\ensuremath{\sim}\ensuremath{\lfloor}\frac{n}{2}\ensuremath{\rfloor}{log}_{2}({N}_{\ensuremath{\omega}}{N}_{\ensuremath{\beta}})$. Here, ${N}_{\ensuremath{\omega}}$ is the number of frequencies in the discretized environment spectrum, and ${N}_{\ensuremath{\beta}}$ is the number of terms in the system-environment interaction. By reproducing two-time correlation functions, i.e., taking $n=2$, we can simulate the Markovian quantum master equation. In our algorithm, the environment on the quantum computer could be even smaller than the system.

arXiv:1908.03759•Physical Review A•Jan 17, 2020•27 citations
We begin with an n-qubit quantum search algorithm and formulate it in terms of quantum walk and adiabatic quantum computation. We then represent and transform the n-qubit search algorithm into a two-level system and hence the single avoided crossing model. We perform and present the analytical calculations and numerical simulations of the dynamics of quantum walk search algorithm and AQC search algorithm in a thermal bath. We use the master equations formulation to represent the open quantum system. We nd out that while generally the performance of algorithms worsen with increase in temperature and the system size, there are interesting features in quantum walk search where there is an optimal low temperature for the best performance for other specied parameters. Similarly for AQC search, the performance generally worsens with increase in temperature, but for specied parameter ranges, the system is more robust against temperature eects.
Adiabatic quantum algorithms represent a promising approach to universal quantum computation. In isolated systems, a key limitation to such algorithms is the presence of avoided level crossings, where gaps become extremely small. In open quantum systems, the fundamental robustness of adiabatic algorithms remains unresolved. Here, we study the dynamics near an avoided level crossing associated with the adiabatic quantum search algorithm, when the system is coupled to a generic environment. At zero temperature, we find that the algorithm remains scalable provided the noise spectral density of the environment decays sufficiently fast at low frequencies. By contrast, higher order scattering processes render the algorithm inefficient at any finite temperature regardless of the spectral density, implying that no quantum speedup can be achieved. Extensions and implications for other adiabatic quantum algorithms will be discussed.
Computing using a continuous-time evolution, based on the natural interaction Hamiltonian of the quantum computer hardware, is a promising route to building useful quantum computers in the near term. Adiabatic quantum computing, quantum annealing, computation by a continuous-time quantum walk, and special purpose quantum simulators all use this strategy. In this work, we carry out a detailed examination of adiabatic and quantum-walk implementation of the quantum search algorithm, using the more physically realistic hypercube connectivity, rather than the complete graph, for our base Hamiltonian. We calculate optimal adiabatic schedules both analytically and numerically for the hypercube and then interpolate between adiabatic and quantum-walk searching, obtaining a family of hybrid algorithms. We show that all of these hybrid algorithms provide the quadratic quantum speedup when run with optimal parameter settings, which we determine and discuss in detail. We incorporate the effects of multiple runs of the same algorithm, noise applied to the qubits, and two types of problem misspecification, determining the optimal hybrid algorithm for each case. Our results reveal a rich structure of how these different computational mechanisms operate and should be balanced in different scenarios. For large systems with low noise and good control, a quantum walk is the best choice, while hybrid strategies can mitigate the effects of many shortcomings in hardware and problem misspecification.
Quantum algorithms for searching for one or more marked items on a ddd-dimensional lattice provide an extension of Grover's search algorithm including a spatial component. We demonstrate that these lattice search algorithms can be viewed in terms of the level dynamics near an avoided crossing of a one-parameter family of quantum random walks. We give approximations for both the level splitting at the avoided crossing and the effectively two-dimensional subspace of the full Hilbert space spanning the level crossing. This makes it possible to give the leading order behavior for the search time and the localization probability in the limit of large lattice size including the leading order coefficients. For d=2d=2d=2 and d=3d=3d=3, these coefficients are calculated explicitly. Closed form expressions are given for higher dimensions.
Recent experiments with increasingly larger numbers of qubits have sparked renewed interest in adiabatic quantum computation, and in particular quantum annealing. A central question that is repeatedly asked is whether quantum features of the evolution can survive over the long time scales used for quantum annealing relative to standard measures of the decoherence time. We reconsider the role of decoherence in adiabatic quantum computation and quantum annealing using the adiabatic quantum master-equation formalism. We restrict ourselves to the weak-coupling and singular-coupling limits, which correspond to decoherence in the energy eigenbasis and in the computational basis, respectively. We demonstrate that decoherence in the instantaneous energy eigenbasis does not necessarily detrimentally affect adiabatic quantum computation, and in particular that a short single-qubit T2{T}_{2}T2​ time need not imply adverse consequences for the success of the quantum adiabatic algorithm. We further demonstrate that boundary cancellation methods, designed to improve the fidelity of adiabatic quantum computing in the closed-system setting, remain beneficial in the open-system setting. To address the high computational cost of master-equation simulations, we also demonstrate that a quantum Monte Carlo algorithm that explicitly accounts for a thermal bosonic bath can be used to interpolate between classical and quantum annealing. Our study highlights and clarifies the significantly different role played by decoherence in the adiabatic and circuit models of quantum computing.
According to recent studies (Amin et al 2008 Phys. Rev. Lett. 100 060503), the effect of a thermal bath may improve the performance of a quantum adiabatic search algorithm. In this paper, we compare the effects of such a thermal environment on the algorithm performance with those of a structured environment similar to the one encountered in systems coupled to an electromagnetic field that exists within a photonic crystal. Whereas for all the parameter regimes explored here, the algorithm performance is worsened by contact with a thermal environment, the picture appears to be different when one considers a structured environment. In this case we show that by tuning the environment parameters to certain regimes, the algorithm performance can actually be improved with respect to the closed system case. Additionally, the relevance of considering the dissipation rates as complex quantities is discussed in both cases. More specifically, we find that the imaginary part of the rates cannot be neglected with the usual argument that it simply amounts to an energy shift and in fact influences crucially the system dynamics.
The quantum open-system simulation is an important category of quantum simulation. By simulating the thermalization process at zero temperature, we can solve the ground-state problem of quantum systems. To realize the open-system evolution on the quantum computer, we need to encode the environment using qubits. However, usually the environment is much larger than the system, i.e., numerous qubits are required if the environment is directly encoded. In this paper, we propose a way to simulate open-system dynamics by reproducing reservoir correlation functions using a minimized Hilbert space. In this way, we only need a small number of qubits to represent the environment. To simulate the $n\mathrm{th}\ensuremath{-}\mathrm{order}$ expansion of the time-convolutionless master equation by reproducing up to nnn-time correlation functions, the number of qubits representing the environment is $\ensuremath{\sim}\ensuremath{\lfloor}\frac{n}{2}\ensuremath{\rfloor}{log}_{2}({N}_{\ensuremath{\omega}}{N}_{\ensuremath{\beta}})$. Here, ${N}_{\ensuremath{\omega}}$ is the number of frequencies in the discretized environment spectrum, and ${N}_{\ensuremath{\beta}}$ is the number of terms in the system-environment interaction. By reproducing two-time correlation functions, i.e., taking n=2n=2n=2, we can simulate the Markovian quantum master equation. In our algorithm, the environment on the quantum computer could be even smaller than the system.