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

19 questions
Filter by
Sorted by
Tagged with
476 views

### Non-universal and non classically simulatable gate set?

The Gottesman-Knill theorem says that many circuits, including all Clifford curcuits can be simulated classically in polynomial time. On the other hand it is believed that there is no polynomial time ...
1 vote
108 views

### An equivalent classical circuit for Hadamard gate

In principle, we can simulate any Quantum circuit via a classical circuit. However, this simulation could be inefficient. (Church-Turing thesis) Together, Hadamard and Toffolli are universal gate sets ...
• 827
238 views

### How do magic states circumvent the Eastin-Knill theorem?

I'm trying to understand magic states and how they circumvent the Eastin-Knill theorem. I understand that these magic states are used to implement non-Clifford gates but how are these magic states ...
• 143
70 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 ...
• 173
1 vote
186 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 ...
• 173
168 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 ...
• 519
210 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 ...
• 519
1 vote
305 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 ...
• 37
99 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 ...
• 1,926
507 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 (...
• 437
200 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 ...
• 680
214 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$-...
• 257
81 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 ...
• 105
535 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 ...
• 1,876
335 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 ...
• 14.8k
359 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 ...
• 14k
5k 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. ...
• 14.8k