Speed up in Bernstein-Vazirani algorithm and Gottesman-Knill theorem

Question

The Bernstein-Vazirani problem:

---

Let $f$ be a function from bit strings of length $n$ to a single bit,

$$f: \{ 0, 1\}^n \to \{0, 1\} $$

thus all input bit strings $x \in \{0,1\}^n$. There exists a secret string $s \in \{0,1\}^n$ such that

$$ f(x) = x\cdot s$$

where $\cdot$ denotes the inner product mod 2. Find $s$ by querying $f$ as a few times as possible.

---

This problem can be solved using 1 query using QFT. The algorithm construction only uses an $X$ gate, Hadamard ($H$) gates, and $CNOT$ gates.

---

Now, according to the Gottesman-Knill theorem, quantum algorithms which utilise only the operations belonging to a certain restricted set (Clifford group $C_n$, which is nothing but the normalizer of the Pauli group $P_n$) are efficiently simulable classically.

This implies that the quantum circuit we construct including the oracle can be implemented efficiently classically. So why do we say this problem can be solved exponentially faster with a quantum computer?

I understand that if you want to develop a classical algorithm then you do have to query the oracle $N$ times... but can't we just implement the entire circuit classically in polynomial time based on the Gottesman-Knill theorem.

What am I missing here? Thank you!

Answer 1

There are two different aspects to your question:

Firstly, nobody should be claiming that you can solve this exponentially faster on a quantum computer. If I evaluate $f(x)$ just $n$ times using $x=1000..0, 01000...0, 00100..0, ... , 00...001$, then each time I find a particular bit value of $s$, and hence I find $s$ with $n$ function calls. This is only polynomially worse than the 1 function call in the quantum algorithm.

So, yes, the circuit can be classically simulated, meaning that there is a polynomial overhead in the simulation. That polynomial takes the number of calls from 1 to $n$. What this algorithm is trying to show you is that quantum algorithms can give you an improvement. It does not claim exponential improvement (you need to go to Simon's algorithm for that).

I should, however, mention the second point: that while you list the gates used: $X$, $H$ and cNOT, you leave out a very important "gate": the oracle itself. Do you know that if you were to decompose the oracle's function in terms of gates that you could certainly write it in terms of just $X$, $H$ and cNOT? Conventional explanations start from it being a reversible classical circuit, so you can decompose it in terms of Toffoli. But Toffoli is not covered by Gottesman-Knill. So, how do you incorporate the action of the oracle into your simulation?