# 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.

16 questions
Filter by
Sorted by
Tagged with
1 vote
59 views

### Gottesman-Knill simulation and Bell states

I have some problems to grasp the interpretation of the Gottesman-Knill theorem. If the first qubit is measured, since $\mathcal{Z} \otimes \mathcal{I}$ does not commute with all the stabilizers, the ...
1 vote
91 views

### Gottesman-Knill theorem -- last measurement step

In the Gottesman-Knill theorem, the stabilizer set is updated after each Clifford gate. These steps are quite simple. At the end, the measurement is simulated. In some on-line explanations, I have ...
105 views

### Understanding the Gottesman-Knill Theorem

I come from a theoretical CS background, and I am trying to gain a better appreciation of the exact formal statement of the Gottesman-Knill theorem in terms that I am more familiar with. My question ...
195 views

### Does Gottesman-Knill theorem apply with any computational basis input?

On Wikipedia, the Gottesman-Knill theorem is said to state the following: A quantum circuit using only the following elements can be simulated efficiently on a classical computer. Preparation of ...
1 vote
183 views

### Stabilizer State - efficient calculation of measurement probabilities - Qiskit

I would like to calculate the probability of measuring some state $U\rho U^\dagger$ in the basis state $b \in (0,1)^{\otimes n}$, i.e. $<b|U\rho U^\dagger|b>$. Now, according to Gottesmann and ...
1 vote
86 views

### Are there non-stabilizer multi-qubit states that are easy to simulate?

The Gottesman-Knill theorem states that the following process is efficiently simulatable on a classical computer: start of with a set of qubits in a computational basis apply any amount of $H, S$ and ...
370 views

### The construction of every element of the Clifford group using H,S and CNOT circuits

I am trying to understand the following theorem: Every element $U\in C_n$ of the Clifford group can be constructed using $H, S, CNOT$ gates. In Nielsen and Chuang's book this is left as an exercise (...
162 views

### Group of commuting Pauli matrices doesn't permit synthesis

I am working on learning grouped measurement and I began by reading this paper by a group out of UChicago showing a method for the synthesis of circuits for the grouped measurement of a set of ...
190 views

### How powerful are boundedly many $T$-gates?

For a natural number $k$ (0 is a natural number), let $T_k$ be the collection of all languages that can be efficiently decided by quantum circuits consisting of Clifford gates and at most $k$ $T$-...
77 views

### In quantum circuits, why does $UNU^\dagger$ act on states in the same way $N$ acts before the operation?

I understand that the Schrodinger picture changes the quantum states, while the Heisenberg picture changes the operators. In this paper The Heisenberg Representation of Quantum Computers, in equations ...
411 views

### Gottesman Knill theorem: why $O(n^2)$ classical operation to keep track of a Clifford gate

Starting from a state stabilized by Pauli matrices, and using only Clifford operations Gottesman Knill theorem ensures us that such algorithm can be classically simulated. Indeed, if I call my initial ...
286 views

### Is it possible to construct Grover search from Clifford gates only?

In the article Is Quantum Search Pratical the authors emphasized that a complexity of an oracle is often neglected when advantages of Grover search are discussed. In the end, a total complexity of the ...
318 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 ...
4k 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. ...