✦ LIBER ✦

Complexity Limitations on Quantum Computation

✍ Scribed by Lance Fortnow; John Rogers

Publisher: Elsevier Science
Year: 1999
Tongue: English
Weight: 141 KB
Volume: 59
Category: Article
ISSN: 0022-0000
DOI: 10.1006/jcss.1999.1651

No coin nor oath required. For personal study only.

✦ Synopsis

We use the powerful tools of counting complexity and generic oracles to help understand the limitations of the complexity of quantum computation. We show several results for the probabilistic quantum class BQP: BQP is low for PP, i.e., PP BQP =PP; There exists a relativized, world, where P=BQP and the polynomial-time hierarchy is infinite; There exists a relativized world, where BQP does not have complete sets; There exists a relativized world, where P=BQP, but P{UP & coUP and one-way functions exist. This gives a relativized answer to an open question of Simon.

📜 SIMILAR VOLUMES

Reflections on quantum computing

✍ Christian S. Calude; Michael J. Dinneen; Karl Svozil 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 110 KB 👁 1 views

Computational complexity on computable m

Computational complexity on computable metric spaces

✍ Klaus Weirauch 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 344 KB

## Abstract We introduce a new Turing machine based concept of time complexity for functions on computable metric spaces. It generalizes the ordinary complexity of word functions and the complexity of real functions studied by Ko [19] et al. Although this definition of TIME as the maximum of a gene

Editorial: Special issue on quantum dots

Editorial: Special issue on quantum dots for quantum computing

✍ Hideaki Matsueda; Jonathan P. Dowling 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 27 KB

Recent progress in the fabrication of nanometer-size structures (especially quantum dots) and measurements at the nanometer scale is going to provide us the freedom to harness fast, and seemingly weak, correlations between atoms in an ensemble-correlations that manifest themselves at the macroscopic

On the Possibility of Quantum Computatio

On the Possibility of Quantum Computation Based on Photon Exchange Interactions

✍ T. Opatrný; G. Kurizki 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 81 KB 👁 3 views

We examine several proposed schemes by Franson et al. for quantum logic gates based on non-local exchange interactions between two photons in a medium. In these schemes the presence of a single photon in a given mode is supposed to induce a large phase shift on another photon propagating in the same

On the Communication Complexity of Lipsc

On the Communication Complexity of Lipschitzian Optimization for the Coordinated Model of Computation

✍ Mehran Mesbahi; George P. Papavassilopoulos 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 140 KB

Experimental Primer on the Trapped Ion Q

Experimental Primer on the Trapped Ion Quantum Computer

✍ D.J. Wineland; C. Monroe; W.M. Itano; B.E. King; D. Leibfried; D.M. Meekhof; C. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 371 KB 👁 2 views

The development of a quantum computer based on a system of trapped atomic ions is described, following the proposal of Cirac and Zoller. Initial results on a two-bit quantum logic gate are presented, and select experimental issues in scaling the system to larger numbers of ions and gates are treated