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
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).