✦ LIBER ✦

Quantum Lower Bounds by Quantum Arguments

✍ Scribed by Andris Ambainis

Publisher: Elsevier Science
Year: 2002
Tongue: English
Weight: 160 KB
Volume: 64
Category: Article
ISSN: 0022-0000
DOI: 10.1006/jcss.2002.1826

No coin nor oath required. For personal study only.

✦ Synopsis

We propose a new method for proving lower bounds on quantum query algorithms. Instead of a classical adversary that runs the algorithm with one input and then modifies the input, we use a quantum adversary that runs the algorithm with a superposition of inputs. If the algorithm works correctly, its state becomes entangled with the superposition over inputs. We bound the number of queries needed to achieve a sufficient entanglement and this implies a lower bound on the number of queries for the computation. Using this method, we prove two new W(`N) lower bounds on computing AND of ORs and inverting a permutation and also provide more uniform proofs for several known lower bounds which have been previously proven via a variety of different techniques.

📜 SIMILAR VOLUMES

Universal Lower Bounds for Quantum Diffu

Universal Lower Bounds for Quantum Diffusion

✍ J.M. Barbaroux; S. Tcheremchantsev 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 220 KB

We study the connections between dynamical properties of Schro dinger operators H on separable Hilbert space H and the properties of corresponding spectral measures. Our main result establishes a relation for the moment of order p of the form H dt L , pÂd (T ). (1) Here L , pÂd (T ) is a function

How to derive a quantum complexity lower

How to derive a quantum complexity lower bound

✍ Tetsuro Nishino 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 204 KB 👁 1 views

Tight Bounds on Quantum Searching

✍ Michel Boyer; Gilles Brassard; Peter Høyer; Alain Tapp 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 210 KB

Landauer counting argument, quantum dist

Landauer counting argument, quantum distribution-function transport equations, and nonequilibrium quantum statistical physics

✍ F.A. Buot; A.K. Rajagopal 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 299 KB

Issues of nonequilibrium quantum statistical physics from the point of view of carrying out numerical computation of ultrafast dynamics, and consequences of the Liouville-von Neumann-Lindblad equation to incorporate dissipative and nonextensive phenomena are discussed.

Quantum oscillator argument against nonr

Quantum oscillator argument against nonreciprocity in linear bi-isotropic media

✍ Clifford M. Krowne 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 82 KB

Using Condon's quantum oscillator methodology to examine the implications for optical rotary beha¨ior of the classical electromagnetic fields, we pro¨ide a simple deri¨ation showing that nonreciprocity is not to be expected in ordinary chiral-like media. Furthermore, we conclude that the only way to

Exciton Bound States in Narrow Quantum W

Exciton Bound States in Narrow Quantum Wells

✍ O. Betbeder-Matibet; M. Combescot; C. Benoit à la Guillaume 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 209 KB 👁 2 views