How are Deutsch-Jozsa and Bernstein-Vazirani algorithms a fair comparison to classical ones

Question

In both of these example algorithms, the Classical one is restricted to a single bit of output, while the Quantum one is allowed to use information exposed from multiple bits. There is no question that more information can be carried by more bits, so it is not surprising that an answer can be obtained faster by measuring more than a single bit in the Quantum algorithm.

If a Classical algorithm were allowed multiple bits of output, for example, it could also produce the solution to the Bernstein-Vazirani computation in a single call. Rather than having to set one bit at a time at the input register across multiple calls, the input could have all bits set to one and read the output of all bits at once, and give the result of an AND operation revealing the secret string.

If the Quantum versions were also restricted to only using a single bit of output, they would not provide any speed up over the Classical versions. So how are these fair performance comparisons between Classical and Quantum computing?

An example Deutsch-Jozsa circuit for a "balanced" function:

            ░ ┌───┐ ░            ░ ┌───┐ ░ ┌─┐
q0_0: ──────░─┤ H ├─░───■────────░─┤ H ├─░─┤M├──────
            ░ ├───┤ ░   │        ░ ├───┤ ░ └╥┘┌─┐
q0_1: ──────░─┤ H ├─░───┼────■───░─┤ H ├─░──╫─┤M├───
      ┌───┐ ░ ├───┤ ░ ┌─┴─┐┌─┴─┐ ░ ├───┤ ░  ║ └╥┘┌─┐
q0_2: ┤ X ├─░─┤ H ├─░─┤ X ├┤ X ├─░─┤ H ├─░──╫──╫─┤M├
      └───┘ ░ └───┘ ░ └───┘└───┘ ░ └───┘ ░  ║  ║ └╥┘
c0: 3/══════════════════════════════════════╩══╩══╩═

"Garcia-Escartin, Juan Carlos & Chamorro-Posada, Pedro. (2011). Equivalent Quantum Circuits" http://arxiv-export-lb.library.cornell.edu/pdf/1110.2998

Rule II: Control Reversal, Corollary II.A states:

CNOT gate with four H gates, one before and one after the control and one before and one after the target, is equivalent to a CNOT operation where control and target are exchanged.

So the above circuit can be transformed into the following:

            ░ ┌───┐      ░ ┌─┐
q0_0: ──────░─┤ X ├──────░─┤M├──────
            ░ └─┬─┘┌───┐ ░ └╥┘┌─┐
q0_1: ──────░───┼──┤ X ├─░──╫─┤M├───
      ┌───┐ ░   │  └─┬─┘ ░  ║ └╥┘┌─┐
q0_2: ┤ X ├─░───■────■───░──╫──╫─┤M├
      └───┘ ░            ░  ║  ║ └╥┘
c0: 3/══════════════════════╩══╩══╩═

And a CNOT gate with a control that is always |1> is equivalent to a NOT gate:

            ░ ┌───┐ ░ ┌─┐
q0_0: ──────░─┤ X ├─░─┤M├──────
            ░ ├───┤ ░ └╥┘┌─┐
q0_1: ──────░─┤ X ├─░──╫─┤M├───
      ┌───┐ ░ └───┘ ░  ║ └╥┘┌─┐
q0_2: ┤ X ├─░───────░──╫──╫─┤M├
      └───┘ ░       ░  ║  ║ └╥┘
c0: 3/═════════════════╩══╩══╩═

So the original circuit behaves like a circuit with no superposition and no entanglement, but simply flips and measures the bits in parallel. Needless to say that a classical circuit can do the same thing.

Below is a Quantum circuit that does maintain superposition and entanglement, doesn't use the "input" register as additional output data, but is restricted to only measuring the single "output" qubit (same restriction as classical circuit):

      ┌───┐ ░            ░ ┌───┐ ░
q0_0: ┤ H ├─░───■────────░─┤ H ├─░────
      ├───┤ ░   │        ░ ├───┤ ░
q0_1: ┤ H ├─░───┼────■───░─┤ H ├─░────
      └───┘ ░ ┌─┴─┐┌─┴─┐ ░ └───┘ ░ ┌─┐
q0_2: ──────░─┤ X ├┤ X ├─░───────░─┤M├
            ░ └───┘└───┘ ░       ░ └╥┘
c0: 1/══════════════════════════════╩═

The measured qubit is a superposition of possible outputs, so for a balanced function could be measured as a 0 or 1. Therefore it may be necessary to evaluate the circuit multiple times before a 1 is measured. Even measuring a 0 many times in a row does not allow one to conclude the function is constant rather than balanced.

Answer 1

Yes, the classical oracle as conventionally expressed has a single bit of output. But one can also rewrite it as a reversible (classical) oracle that operates as $$ x,y\mapsto x,y\oplus f(x). $$ The classical conclusion must of course still be the same because, effectively, there's only one bit of output as the $n$ bits making up $x$ cannot change.

The quantum oracle is exactly the same as this classical oracle (except that it allows you to input superpositions of basis states). This is the important point in making a fair comparison. If you input basis states, you get basis state outputs where only a single bit has changed.

The secret sauce of quantum is this "phase kickback" mechanism that somehow permits all the output bits to change even though it looks like they shouldn't, enabling you to access up to $n+1$ bits of information when you measure the output.

Answer 2

Even in classical setting you have multiple bits input into the evaluated function provided your function have more variables than one.

However, on classical computer you cannot input multiple inputs at one time (neglecting parallel computing, or multiple CPU cores). While thanks to superposition you can have more than one input to the function on a quantum computer. This is the main difference between classical and quantum computing paradigms.

Number of output qubits does not matter as an answer provided by the algorithm is binary - balanced or constant function. Classical computer for example can say 0 for constant function and 1 for balanced. Quantum computer (DJ algorithm) says 000...0 for constant function and any other bit string for balanced function. This is still binary answer regardless length of the bit string returned as only two possible interpretations of the results take place.