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
4
votes
3
answers
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
1
answer
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
4
votes
1
answer
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
2
votes
1
answer
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
1
answer
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
4
votes
0
answers
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
5
votes
1
answer
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
1
answer
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
2
votes
0
answers
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
5
votes
2
answers
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
2
votes
1
answer
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
5
votes
1
answer
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
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 ...
- 105
3
votes
1
answer
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
3
votes
1
answer
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
3
votes
1
answer
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
17
votes
1
answer
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
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, ...
- 1,116
22
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 ...
