What is arithmetic circuits indeed? I know that Boolean circuits and Arithmetic circuits are two different ways of representing a computation. But I want to know how to instantiate arithmetic circuits and it's computation in practice. For example, when we multiply two l bits numbers, we say that arithmetic circuits are efficient because it represent those two nums as two field elements, and only need 1 multiplication gate. But I don't understand: don't we have to represent those two nums in bits in machine code? And do we have to represent that multiplication gate in basic blocks such as and-gate/xor-gate...or is there a real circuit structure is multiplication gate?
Sorry for such a dummy question, but this confuse me for quite a long time and I can't find the answer by myself. So could anyone give me some guide or some paper to this question?
Great thanks.
The whole point is that in the Aritmetic Circuit (AC) model we take a field and use field operations (+,*) as building blocks.
Each field operation is represented as a single output multiple input gate.
The total number of gates and the depth of the AC are typical measures of complexity. Size and bit structure of inputs does not explicitly come into it, each operation is considered of some fixed complexity.
The goal is to find the minimum complexity circuit realizing a certain formula.