Skip to main content
Share Your Experience: Take the 2024 Developer Survey

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
4 votes
1 answer
219 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 ...
Karim's user avatar
  • 143
2 votes
1 answer
67 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 ...
JMark's user avatar
  • 173
1 vote
1 answer
147 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 ...
JMark's user avatar
  • 173
4 votes
0 answers
138 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 ...
trillianhaze's user avatar
5 votes
1 answer
208 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 ...
trillianhaze's user avatar
1 vote
1 answer
258 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 ...
Coryn7's user avatar
  • 37
1 vote
0 answers
93 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 ...
sheesymcdeezy's user avatar
5 votes
2 answers
449 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 (...
Gadi A's user avatar
  • 437
2 votes
1 answer
179 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 ...
Cuhrazatee's user avatar
5 votes
1 answer
207 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$-...
Haim's user avatar
  • 257
2 votes
1 answer
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 ...
FSeed's user avatar
  • 105
3 votes
1 answer
509 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 ...
Marco Fellous-Asiani's user avatar
3 votes
1 answer
319 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 ...
Martin Vesely's user avatar
3 votes
1 answer
343 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 ...
KAJ226's user avatar
  • 13.9k
17 votes
1 answer
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. ...
Martin Vesely's user avatar
14 votes
2 answers
3k 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, ...
user2723984's user avatar
  • 1,106
20 votes
1 answer
6k views

Twirling Quantum Channels: Pauli and Clifford Twirling

I am currently working through some papers related with approximations of more general quantum channels such as amplitude and phase damping channels to Pauli channels. The reason to do so is so that ...
Josu Etxezarreta Martinez's user avatar