Questions tagged [gottesman-knill]

Questions directed to the Gottemsman-Knill theorem, which states that quantum circuits consisting of elements from the Clifford group are classically efficient to simulate.

Filter by
Sorted by
Tagged with
3
votes
1answer
37 views

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 ...
8
votes
1answer
405 views

Why are non-Clifford gates more complex than Clifford gates?

There are two groups of quantum gates - Clifford gates and non-Clifford gates. Representatives of Clifford gates are Pauli matrices $I$, $X$, $Y$ and $Z$, Hadamard gate $H$, $S$ gate and $CNOT$ gate. ...
7
votes
2answers
2k views

Why doesn't the Gottesman-Knill theorem render quantum computing almost useless?

The Gottesman-Knill theore states (from Nielsen and Chuang) Suppose a quantum computation is performed which involves only the following elements: state preparations in the computational basis, ...