Classical bit-operation cost

For a classical query algorithm Classical query algorithm, bit-operation cost is the number of transitions of a declared multitape Turing machine over a fixed finite alphabet; the $k$-tape transition reads and writes one symbol on each of its $k\ge 1$ tapes and moves each head once per transition (Multitape and nondeterministic Turing machine variants). It includes random-bit generation, any encoding work actually performed by that machine on declared public data or received replies, address formation, reading and writing every bit of an oracle reply, comparison/postprocessing, and writing the classical output. The abstract instance encoding in Input encoding and size for algorithmic tasks fixes the size parameter; it supplies neither a readable hidden input nor an encoding procedure to execute. The fair-bit machine convention is supplied by Probabilistic polynomial time machine interface. The oracle invocation itself is one separately counted query action; its returned bits are not free to process.

For a query with an $a(n)$-bit address and a $b(n)$-bit reply, the machine's charged work includes forming the address and processing the $b(n)$ reply symbols. A claimed time bound also specifies whether it is worst-case over promised inputs and random tapes, as in Probabilistic polynomial time machine interface. Query, nonoracle quantum gate, measurement, and classical bit costs remain distinct.