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
1
vote
1
answer
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 ...
- 65
1
vote
1
answer
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 ...
- 65
4
votes
0
answers
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 ...
- 429
4
votes
1
answer
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 ...
- 429
1
vote
1
answer
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 ...
- 37
1
vote
0
answers
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 ...
- 1,654
5
votes
2
answers
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 (...
- 427
2
votes
1
answer
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 ...
- 611
5
votes
1
answer
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$-...
- 247
2
votes
1
answer
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 ...
- 105
3
votes
1
answer
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 ...
- 1,404
3
votes
1
answer
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 ...
- 13.6k
3
votes
1
answer
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 ...
- 13.7k
16
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. ...
- 13.6k
13
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,056
19
votes
1
answer
5k
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 ...
