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

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.

• Welcome to QCSE. What do you mean by "while the Quantum one is allowed to use information exposed from multiple bits"? Quantum algorithms operate on qubits, which are not quite the same as bits. Apr 11 at 19:15
• I'm referring to the qubits in the "input" register that are being measured and providing additional information that is not available with just a single qubit in the "output" register. Apr 12 at 15:50

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.

• So, if I understand you correctly, you are saying that surrounding the given Quantum oracle with Hadamard gates, thereby reversing the behavior of the oracle to one that sends data out of the input qubits (kickback), and converts it to a parallel computation (n + 1 bits), is a valid comparison to the given Classical oracle (which must remain a serial computation) because the original oracles are the same. But my question is whether this is a fair restriction since a Classical parallel computation that would be just as fast as the Quantum computation is possible. Apr 13 at 16:55
• But a classical parallel computation still requires you to use the oracle $n$ times, whether that's because you do it in serial or because you have $n$ copies of the oracle and do it in parallel. Quantum only makes one oracle call. It's not about the running time, but the total number of oracle calls. Parallel vs serial doesn't change that. Apr 14 at 10:09
• I don't see why you would need to call the oracle multiple times in a classical parallel computation. I have added specific examples to the post to try to clarify my question. Apr 14 at 16:43

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.

• In the Bernstein-Vazirani case the classical algorithm is restricted to evaluating the function once for each bit in the input string, each input x being a different power of 2. But you can have multiple inputs at once by setting all the bits in x to one. If the Classical algorithm were allowed multiple output bits, you could in fact obtain the answer in a single call just as you can with the Quantum computation. Apr 13 at 17:18