Can quantum circuits/operations have truth tables?

Question

In the caption for the following figure, the word "truth table" is put inside a quotation. I am wondering if this means that the truth table the caption refers to isn't exactly a real truth table? If so, why?

Answer 1

Quoting Wikipedia, a truth table is a table "which sets out the functional values of logical expressions on each of their functional arguments".

Thus, a quantum operation cannot have a literal truth table, since it would need an infinite number of rows in it, one for each quantum state it can act on!

Here we're looking at a quantum variant of it, which defines the effect of a quantum operation on each of the basis states. This allows us to figure out its effect on any superposition states using linearity of both superposition and quantum gates. This table, for example, allows you to see that the effect of applying this circuit $U$ to $\frac1{\sqrt2}(|00\rangle + |10\rangle)$ will be

$$U\frac1{\sqrt2}(|00\rangle + |10\rangle) = \frac1{\sqrt2}(U|00\rangle + U|10\rangle) = \\ = \frac1{\sqrt2}\big(\frac1{\sqrt2}(|00\rangle + |11\rangle) + \frac1{\sqrt2}(|00\rangle - |11\rangle)\big) = |00\rangle$$

Answer 2

I think the authors are just taking a very strict definition of truth table, requiring a single deterministic answer for each input.

With this table each input gives you a guaranteed output, but those outputs are probabilistically going to be one of two possible states when measured. (Instead of a single guaranteed output like the truth table for a NAND gate in classical logic.)

For example:

from qiskit import *

qc = QuantumCircuit(2)
# qc.x(0)
# qc.x(1)
qc.h(0)
qc.cx(0, 1)
qc.measure_all()
backend = Aer.get_backend("qasm_simulator")
job = execute(qc, backend, shots=1024)
print(job.result().get_counts())

This should give you output something like {'11': 511, '00': 513}, which is what you would expect by examining the table and seeing that when the input state is $|00\rangle$ (which is Qiskit's default initialization state), the output will have coefficients for states $|00\rangle$ and $|11\rangle$ that are both $\frac{1}{\sqrt{2}}$.

The coefficients are probability amplitudes, so to find the actual probability of the state: $$\left| \frac{1}{\sqrt{2}} \right|^2 = 0.5$$

Uncommenting the two x()'s will change the input state from $|00\rangle$ to $|11\rangle$, and the new output will be something like {'01': 512, '10': 512}.

Which is what you would expect from the table.

So for a single experiment you could not say for certain, "your output will be $x$". You could only say, "for this input you will get one of these possible outputs".

Edit: You could contrive a quantum circuit where the values always stayed with 100% probability in one state or another, thus giving you deterministic single outcomes for a given input. Then "truth table" would be strictly accurate, but all you will have done is make a classical computer with extra steps. You would never be able to use superposition or any of the features of the quantum computer that make it different than the classical ones.