Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Conference papers

Adversary lower bounds for nonadaptive quantum algorithms

Pascal Koiran 1, * Jürgen Landes 2 Natacha Portier 1, * Penghui yao 3 
* Corresponding author
1 LIP - Laboratoire de l'Informatique du Parallélisme
2 The University of Manchester School of Mathematics
3 LCS - State Key Laboratory of Computer Science [Beijing]
Abstract : We present general methods for proving lower bounds on the query complexity of nonadaptive quantum algorithms. Our results are based on the adversary method of Ambainis.
Keywords : query complexity lower bound quantum computing nonadaptive algorithm adversary mathod
Document type :
Conference papers
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download
https://hal-ens-lyon.archives-ouvertes.fr/ensl-00260279
Contributor : Natacha Portier Connect in order to contact the contributor
Submitted on : Wednesday, April 9, 2008 - 11:29:09 AM
Last modification on : Saturday, September 11, 2021 - 3:17:05 AM
Long-term archiving on: : Friday, November 25, 2016 - 10:34:09 PM

Files

Vignette du document
nonadaptQuantum.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : ensl-00260279, version 2
  • ARXIV : 0804.1440

Collections

ENS-LYON | CNRS | INRIA | UNIV-LYON1 | UDL

Citation

Pascal Koiran, Jürgen Landes, Natacha Portier, Penghui yao. Adversary lower bounds for nonadaptive quantum algorithms. WoLLIC 2008 15th Workshop on Logic, Language, Information and Computation, Jul 2008, Edinburgh, United Kingdom. ⟨ensl-00260279v2⟩

Export

BibTeX TEI DC DCterms EndNote Datacite

Share

Metrics

Record views

77

Files downloads

187