Adversary lower bounds for nonadaptive quantum algorithms

Pascal Koiran 1, * Jürgen Landes 2 Natacha Portier 1, * Penghui Yao 3
* Auteur correspondant
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
Type de document :
Communication dans un congrès
WoLLIC 2008 15th Workshop on Logic, Language, Information and Computation, Jul 2008, Edinburgh, United Kingdom. Springer, 2008, LNCS series (FoLLI-LNAI subseries)
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger
https://hal-ens-lyon.archives-ouvertes.fr/ensl-00260279
Contributeur : Natacha Portier <>
Soumis le : mercredi 9 avril 2008 - 11:29:09
Dernière modification le : mardi 24 avril 2018 - 13:52:29
Document(s) archivé(s) le : vendredi 25 novembre 2016 - 22:34:09

Fichiers

nonadaptQuantum.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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

Collections

INRIA | LIP | ENS-LYON | UNIV-LYON1

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. Springer, 2008, LNCS series (FoLLI-LNAI subseries). 〈ensl-00260279v2〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

163

Téléchargements de fichiers

113

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD