The adiabatic theorem has been recently used to design quantum algorithms of a new kind, where the computer evolves slowly enough so that it remains near its instantaneous ground state which tends solution [Farhi et al., quant-ph/0001106]. We apply this time-dependent Hamiltonian approach Grover's problem, i. e., searching marked item in an unstructured database. find that, by adjusting evolution rate as keep on each infinitesimal time interval, total running is order $\sqrt{N}$, $N$ number...

We propose a new method for designing quantum search algorithms finding "marked" element in the state space of classical Markov chain. The algorithm is based on walk \'a la Szegedy (2004) that defined terms main idea to apply phase estimation order implement an approximate reflection operator. This operator then used amplitude amplification scheme. As result we considerably expand scope previous approaches Ambainis and (2004). Our combines benefits these being able find marked elements,...

Understanding NP-complete problems is a central topic in computer science (NP stands for nondeterministic polynomial time). This why adiabatic quantum optimization has attracted so much attention, as it provided new approach to tackle using computer. The efficiency of this limited by small spectral gaps between the ground and excited states computer's Hamiltonian. We show that statistics can be analyzed novel way, borrowed from study disordered systems statistical mechanics. It turns out due...

Continuous-time quantum walks provide a natural framework to tackle the fundamental problem of finding node among set marked nodes in graph, known as spatial search. Whether search by continuous-time walk provides quadratic advantage over classical random has been an outstanding problem. Thus far, this is obtained only for specific graphs or when single underlying graph marked. In article, we new algorithm that completely resolves this: our can find any with number nodes, time quadratically...

We propose a new method for designing quantum search algorithms forfinding "marked" element in the state space of classical Markovchain. The algorithm is based on walk à la Szegedy [25] that defined terms Markov chain. main idea to apply phase estimation quantumwalk order implement an approximate reflection operator. Thisoperatoris then used amplitude amplification scheme. As result weconsiderably expand scope previous approaches ofAmbainis [6] and [25]. Our combines benefits these beingable...

Besides the traditional circuit-based model of quantum computation, several algorithms based on a continuous-time Hamiltonian evolution have recently been introduced, including for instance walk as well adiabatic algorithms. Unfortunately, very little is known today about behavior these in presence noise. Here, we perform fully analytical study resistance to noise using perturbation theory combined with theoretical random matrices drawn from Gaussian orthogonal ensemble, whose elements vary...

It is known that quantum correlations exhibited by a maximally entangled qubit pair can be simulated with the help of shared randomness, supplemented additional resources, such as communication, postselection or nonlocal boxes. For instance, in case projective measurements, it possible to solve this problem protocols using one bit communication making use box. We show reduces distributed sampling problem. give new method obtain samples from biased distribution, starting random variables...

We show that almost all known lower bound methods for communication complexity are also bounds the information complexity. In particular, we define a relaxed version of partition Jain and Klauck prove it any function. Our subsumes norm based (e.g. factorization method) rectangle-based rectangle/corruption bound, smooth rectangle discrepancy bound), except bound. result uses new connection between rectangles zero-communication protocols where players can either output value or abort....

We introduce a new quantum adversary method to prove lower bounds on the query complexity of state generation problem. This problem encompasses both, computation partial or total functions and preparation target states. There has been hope for quite some time that might be route tackle GRAPH-ISOMORPHISM show related INDEX-ERASURE our leads bound square root N which matches an upper obtained via reduction search elements. closes open first raised by Shi [FOCS'02]. Our approach is based two...

Rejection sampling is a well-known method to sample from target distribution, given the ability distribution. The has been first formalized by von Neumann [1951] and many applications in classical computing. We define quantum analogue of rejection sampling: black box producing coherent superposition (possibly unknown) states with some amplitudes, problem prepare same states, albeit different amplitudes. main result this article tight characterization query complexity state generation...

One of the most important algorithmic applications quantum walks is to solve spatial search problems. A widely used algorithm for this problem, introduced by Childs and Goldstone [Phys. Rev. 70, 022314 (2004)], finds a marked node on graph $n$ nodes via continuous-time walk. This said be optimal if it can find any in $O(\sqrt{n})$ time. However, given graph, no general conditions optimality are known previous works demonstrating certain graphs required an instance-specific analysis. In fact,...

The bosonic quantum channels have recently attracted a growing interest, motivated by the hope that they open tractable approach to generally hard problem of evaluating channel capacities. These studies, however, always been restricted memoryless channels. Here, it is shown classical capacity Gaussian with memory can be significantly enhanced if entangled symbols are used instead product symbols. For example, photonic 70%-correlated thermal noise one-third shot about 11% when using 3.8-dB...

We derive both numerically and analytically Bell inequalities quantum measurements that present enhanced resistance to detector inefficiency. In particular, we describe several which appear be optimal with respect inefficient detectors for small dimensionality $d=2,3,4$ two or more measurement settings at each side. also generalize the family of described by Collins et al. [Phys. Rev. Lett. 88, 040404 (2002)] take into account inefficiency detectors. addition, consider possibility pairs...

Adiabatic quantum optimization has attracted a lot of attention because small scale simulations gave hope that it would allow to solve NP-complete problems efficiently. Later, negative results proved the existence specifically designed hard instances where adiabatic requires exponential time. In spite this, there was still this not happen for random problems. This is an important issue since are good model can be solved by current classical solvers, which efficient algorithm therefore...

Rejection sampling is a well-known method to sample from target distribution, given the ability distribution. The has been first formalized by von Neumann (1951) and many applications in classical computing. We define quantum analogue of rejection sampling: black box producing coherent superposition (possibly unknown) states with some amplitudes, problem prepare same states, albeit different amplitudes. main result this paper tight characterization query complexity state generation problem....

The fundamental problem of sampling from the limiting distribution quantum walks on networks, known as mixing, finds widespread applications in several areas information and computation. Of particular interest most these is minimum time beyond which instantaneous probability walk remains close to this distribution, ``quantum mixing time''. However, quantity only for a handful specific networks. In Letter, we prove an upper bound almost all i.e., fraction networks our holds, goes one...

We analyze three different quantum search algorithms, namely, the traditional circuit-based Grover's algorithm, its continuous-time analog by Hamiltonian evolution, and local adiabatic evolution. show that these algorithms are closely related in sense they all perform a rotation, at constant angular velocity, from uniform superposition of states to solution state. This makes it possible implement two Hamiltonian-evolution on conventional circuit, while keeping quadratic speedup original...

We present an adiabatic quantum algorithm for the abstract problem of searching marked vertices in a graph, or spatial search. Given random walk (or Markov chain) $P$ on graph with set unknown vertices, one can define related absorbing ${P}^{'}$ where outgoing transitions from are replaced by self-loops. build Hamiltonian $H(s)$ interpolated chain $P(s)=(1\ensuremath{-}s)P+{\mathit{sP}}^{'}$ and use it to drive initial superposition over all vertices. The condition implies that, any...

Spatial search by a discrete-time quantum walk can find marked node on any ergodic, reversible Markov chain $P$ quadratically faster than its classical counterpart, i.e., in time that is the square root of hitting $P$. However, framework continuous-time walks, it was previously unknown whether such general speedup possible. In fact, this framework, widely used algorithm Childs and Goldstone fails to achieve speedup. Furthermore, not clear how apply for searching article we aim reconcile...

The problem of sampling from the stationary distribution a Markov chain finds widespread applications in variety fields. time required for to converge its is known as classical mixing time. In this article, we deal with analog quantum algorithms mixing. First, provide an algorithm that, given chain, allows us sample that scales sum square root and hitting Our makes use framework interpolated walks relies on Hamiltonian evolution conjunction von Neumann measurements. There also exists...