I am trying to ascertain a precise understanding of the relationship between the quantum query model of complexity and the quantum circuit model of complexity. Specifically, is there an established mapping between these two models of complexity?

I have yet to find a precise account of their relationship, but my reading of work by Yao (1993) is that they are polynomially related. Is this the extent of our understanding? Is it even sensible for a mapping between these two models of complexity to exist or should we be satisfied in the notion that they address two separate sets of questions (i.e. different tools for different jobs)?

I've considered that perhaps we may view the quantum circuit complexity as a component of the query complexity in that it might be used to establish the complexity of an quantum oracle as implemented in practice. While not a mapping, is that a plausible way of connecting the two or are there additional considerations?

P.S. I was not able to find a non-paywalled version of Yao's paper, if anyone has one they could link for the purpose of this question that would be excellent.


1 Answer 1


I've come across a paper (published in 2009) by Nishimura and Ozawa that appears to wrap up this line of inquiry. From my reading, the upshot of the paper is this:

The quantum query and circuit models of complexity are "perfectly equivalent", meaning that they can simulate one another with:

  • Zero error
  • A constant time overhead

Regarding the second point, this is my interpretation of "perfectly equivalent" – put another way, my interpretation may not be correct and it may be that they can simulate one another with zero error and a polynomial time, rather than constant time, overhead.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.