Decrease in query complexity for quantum computers with superposition of circuits

Author(s): M. Araújo, Č. Brukner

Title of Conference/Proceeding: Joint Annual Meeting of the Austrian Physical Society and the Swiss Physical Society

Date of Conference:

Location of Conference: Johannes Kepler University Linz

Volume: 45

DOI: -

Link: Link to publication


A new model of quantum computation was introduced by Chiribella et al. in arXiv:0912.0195, in which the structure of the quantum circuits is entangled with a control quantum system. The new model is proven to allow the realization of tasks impossible in standard quantum computation, but the question whether it is more powerful in the complexity sense was left open. Here we answer this question in the affirmative, by showing a promise problem that has query complexity O(n) on a quantum computer with superposition of circuits, whereas the best known quantum algorithm has query complexity O(n2).

Brukner Group Brukner Group