# Circuits with oracles vs. Turing Machines with oracles

Put simply: what is the correspondance between Turing machines with oracles, and uniform circuit families with oracles? How are the latter defined in order to obtain the same computational model, for a given oracle Turing machine?

This may be an elementary question, but it is not obvious where to look, and I'm the sort of person who likes to make sure that my foundations are using good-quality mortar. If there is a standard reference, please point me to it. (Papadimitriou's book, for instance, does not seem to describe circuits with oracles at all.)

My working hypothesis is this: a uniform circuit family with access to an oracle (e.g. for solving an NP-complete problem) is defined as follows:

• One defines an infinite family of "oracle gates" On , one for each circuit size n, each of which compute a function fn : {0,1}cn → {0,1} for some constant c.

• The functions fn computed by the oracle gates On should be "uniform" in the following sense: for any n < N and x ∈ {0,1}n, we require fn(x) = fN( 0c(N−n) x ) --- that is, the oracle gates must use a consistent and extensbile "encoding" of their inputs.

• One then defines a uniform circuit family, where the oracle gates are among the allowed operations to the circuit, restricting the circuit for input size n to use the gate On.

I imagine that some of the choices above may be arbitrarily fixed without losing any generality. What I am interested in is a reference for the correspondence, or at least a description of how to modify the description above to obtain the standard one.

• Since I know you work in quantum information, I would recommend John Watrous' survey on Quantum computational complexity, where he also talks about oracles in quantum circuits and querying the oracle in superposition. – Robin Kothari Aug 25 '10 at 16:26
• Watrous' article is also a good reference. But what it turned out I needed in this case was to be somehow disabused of the idea that anyone would want to define a relativized circuit family in a way that didn't correspond to just testing the same predicate for different finite string lengths, by being reminded that the semantics of an oracle classically is to indicate membership in some set. As it turned out, drawings of circuit gates with the symbols "∈A?" on them was all I needed. – Niel de Beaudrap Aug 26 '10 at 0:03