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

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!

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?

• Thank you for taking your time and answer my question. The exponential speed up is from what I see in the literature and it's all claimed that Bernstein-Vazirani provides an exponential speed up... Now, about the Oracle, the way I see people implement this dot product operation for the Oracle is using only CNOTs gate (do a CNOT wherever there is a 1 in the secret bit-string 's')... So are you saying that this doesn't need to be the case? That is, we can implement this dot-product operation differently, not using only CNOT operations? Commented May 4, 2020 at 1:51
• There are many different ways that you can implement an algorithm. If there's a way that can be done just with gates from the Clifford set, then great. As I say, this algorithm is NOT one with an exponential improvement (I would like to see a link to claims that it does), so there is no problem with being able to simulate it. Mostly I wanted to make the point that you have to be explicit about the consideration. It's also important if you move on to look at Simon's algorithm which does show an exponential speedup, but the gates around the oracle are also just Clifford gates. Commented May 4, 2020 at 7:38
• I agree that it has polynomial (linear) speed-up. That's why I asked the question because I though I saw claims about exponential speed-up. Like your answer here: quantumcomputing.stackexchange.com/a/3996/9858 However, I now realized that the exponential speed up people referring to is the Recursive Bernstein-Vazarini algorithm. Commented May 4, 2020 at 19:39