Jérémie Roland

Jérémie Roland

Auto-generated profile, based on publicly available information

Jérémie Roland

Universite Libre de Bruxelles

Research Focus & Metrics

Academic Career Length

25Years (2002-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
26 March 2002 in Physical Review A
Verified
Journal Article
Closed access
PDF file
JRJérémie Roland
Jérémie Roland
NCNicolas J. Cerf
Nicolas J. Cerf
The adiabatic theorem has been recently used to design quantum algorithms of a new kind, where the quantum computer evolves slowly enough so that it remains near its instantaneous ground state, which tends to the solution. We apply this time-dependent Hamiltonian approach to Grover’s problem, i.e., searching a marked item in an unstructured database. We find that by adjusting the evolution rate of the Hamiltonian so as to keep the evolution adiabatic on each infinitesimal time interval, the total running time is of order N, where N is the number of items in the database. We thus recover the advantage of Grover’s standard algorithm as compared to a classical search, scaling as N. This is in contrast with the constant-rate adiabatic approach of Farhi et al. (e-print quant-ph/0001106), where the requirement of adiabaticity is expressed only globally, resulting in a time of order N.

1 January 2011 in SIAM Journal on Computing
Verified
Journal Article
Closed access
FMFrédéric Magniez
Frédéric Magniez
ANAshwin Nayak
Ashwin Nayak
JRJérémie Roland
Jérémie Roland
MSMiklos Santha
Miklos Santha
We propose a new method for designing quantum search algorithms for finding a “marked” element in the state space of a classical Markov chain. The algorithm is based on a quantum walk à la Szegedy [Quantum speed-up of Markov chain based algorithms, in Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, 2004, pp. 32–41] that is defined in terms of the Markov chain. The main new idea is to apply quantum phase estimation to the quantum walk in order to implement an approximate reflection operator. This operator is then used in an amplitude amplification scheme. As a result we considerably expand the scope of the previous approaches of Ambainis [Quantum walk algorithm for Element Distinctness, in Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, 2004, pp. 22–31] and Szegedy (2004). Our algorithm combines the benefits of these approaches in terms of being able to find marked elements, incurring the smaller cost of the two, and being applicable to a larger class of Markov chains. In addition, it is conceptually simple and avoids some technical difficulties in the previous analyses of several algorithms based on quantum walk.

24 June 2010 in Proceedings of the National Academy of Sciences
Verified
Journal Article
Closed access
BABoris Altshuler
Boris Altshuler
HKHari Krovi
Hari Krovi
JRJérémie Roland
Jérémie Roland
Understanding NP-complete problems is a central topic in computer science (NP stands for nondeterministic polynomial time). This is why adiabatic quantum optimization has attracted so much attention, as it provided a new approach to tackle NP-complete problems using a quantum computer. The efficiency of this approach is limited by small spectral gaps between the ground and excited states of the quantum computer’s Hamiltonian. We show that the statistics of the gaps can be analyzed in a novel way, borrowed from the study of quantum disordered systems in statistical mechanics. It turns out that due to a phenomenon similar to Anderson localization, exponentially small gaps appear close to the end of the adiabatic algorithm for large random instances of NP-complete problems. This implies that unfortunately, adiabatic quantum optimization fails: The system gets trapped in one of the numerous local minima.

21 March 2005 in Physical Review A
Verified
Journal Article
Closed access
PDF file
JRJérémie Roland
Jérémie Roland
NCNicolas J. Cerf
Nicolas J. Cerf
Besides the traditional circuit-based model of quantum computation, several quantum algorithms based on a continuous-time Hamiltonian evolution have recently been introduced, including for instance continuous-time quantum walk algorithms as well as adiabatic quantum algorithms. Unfortunately, very little is known today about the behavior of these Hamiltonian algorithms in the presence of noise. Here, we perform a fully analytical study of the resistance to noise of these algorithms using perturbation theory combined with a theoretical noise model based on random matrices drawn from the Gaussian orthogonal ensemble, whose elements vary in time and form a stationary random process.

14 October 2022 in Physical Review Letters
Verified
Journal Article
Closed access
PDF file
SASimon Apers
Simon Apers
SCShantanav Chakraborty
Shantanav Chakraborty
LNLeonardo Novo
Leonardo Novo
JRJérémie Roland
Jérémie Roland
Continuous-time quantum walks provide a natural framework to tackle the fundamental problem of finding a node among a set of marked nodes in a graph, known as spatial search. Whether spatial search by continuous-time quantum walk provides a quadratic advantage over classical random walks has been an outstanding problem. Thus far, this advantage is obtained only for specific graphs or when a single node of the underlying graph is marked. In this Letter, we provide a new continuous-time quantum walk search algorithm that completely resolves this: our algorithm can find a marked node in any graph with any number of marked nodes, in a time that is quadratically faster than classical random walks. The overall algorithm is quite simple, requiring time evolution of the quantum walk Hamiltonian followed by a projective measurement. A key component of our algorithm is a purely analogue procedure to perform operations on a state of the form e−tH2|ψ⟩, which, for a given Hamiltonian H, only requires evolving H for time scaling as t. This allows us to quadratically fast-forward the dynamics of a continuous-time classical random walk. The applications of our Letter thus go beyond the realm of quantum walks and can lead to new analog quantum algorithms for preparing ground states of Hamiltonians or solving optimization problems.

11 June 2007
Verified
Conference Paper
Open access
FMFrederic Magniez
Frederic Magniez
ANAshwin Nayak
Ashwin Nayak
JRJeremie Roland
Jeremie Roland
MSMiklos Santha
Miklos Santha
We propose a new method for designing quantum search al- gorithms for finding a "marked" element in the state space of a classical Markov chain. The algorithm is based on a quantum walka la Szegedy (25) that is defined in terms of the Markov chain. The main new idea is to apply quantum phase estimation to the quantum walk in order to imple- ment an approximate reflection operator. This operator is then used in an amplitude amplification scheme. As a re- sult we considerably expand the scope of the previous ap- proaches of Ambainis (6) and Szegedy (25). Our algorithm combines the benefits of these approaches in terms of being able to find marked elements, incurring the smaller cost of the two, and being applicable to a larger class of Markov chain. In addition, it is conceptually simple, avoids several technical diculties in the previous analyses, and leads to improvements in various aspects of several algorithms based on quantum walk.