17 votes

Twirling Quantum Channels: Pauli and Clifford Twirling

Definitions Denoting the Haar measure of some function $f\left(x\right)$ over $d$-dimensional unitaries as $\int_{\mathrm U\left(d\right)}f\left(x\right)d\mu\left(x\right)$, twirling some arbitrary ...
user avatar
  • 3,397
13 votes
Accepted

Why doesn't the Gottesman-Knill theorem render quantum computing almost useless?

To my mind, this theorem is not very well stated in this form, if taken out of context. Where it says "phase gates", this may be misleading. It means specifically just $S=\sqrt{Z}$ and not what I ...
user avatar
  • 46.1k
10 votes
Accepted

Why are non-Clifford gates more complex than Clifford gates?

Yes, you are correct. Non-Clifford gates cannot be transversely implemented, instead implementation generally requires distilling magic states or Toffoli states. In practice this requires ...
user avatar
4 votes

Why doesn't the Gottesman-Knill theorem render quantum computing almost useless?

Another way to think about this: To simulate what goes on in a quantum computer we have to do a lot of matrix math using $(2^N \times 2^N)$ matrices$^1$, and the action of (most) of the clifford gates ...
user avatar
  • 4,527
4 votes
Accepted

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

The diffusion operator is a multi controlled not operation (modulo some hadamards). It's not a Clifford operation. Also any useful oracle you'd use with Grover's algorithm won't be Clifford operations ...
user avatar
  • 21.8k
3 votes
Accepted

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

You can pretty easily prove by counting that specifying a stabilizer operation or a stabilizer state requires $\Omega(n^2)$ bits. If you're not tracking some of those bits, your simulator is ...
user avatar
  • 21.8k
2 votes
Accepted

Speed up in Bernstein-Vazirani algorithm and Gottesman-Knill theorem

There are two different aspects to your question: Firstly, nobody should be claiming that you can solve this exponentially faster on a quantum computer. If I evaluate $f(x)$ just $n$ times using $x=...
user avatar
  • 46.1k
2 votes
Accepted

Group of commuting Pauli matrices doesn't permit synthesis

It probably doesn't work because $X_0 X_1 Y_2 Y_3 \cdot X_0 Y_1 Y_2 X_3 \cdot Y_0 X_1 X_2 Y_3 = Y_0 Y_1 X_2 X_3$ so you can't isolate all four from each other. The system is degenerate. Just drop one ...
user avatar
  • 21.8k
2 votes

How powerful are boundedly many $T$-gates?

I think your hierarchy collapses, or at least would never get beyond $P$, following the top-line results of Bravyi and Gosset. Bravyi and Gosset's paper gives an algorithm to classically simulate a ...
user avatar
  • 6,767
2 votes

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

Here's a constructive proof in the form of code that takes the tableau representation of an operation and returns an explicit list of operations that produce the operation. The code basically works by ...
user avatar
  • 21.8k
1 vote
Accepted

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

I think that you can get $M'|\psi_1\rangle = |\psi_2\rangle$ by the following: $U(|0\rangle|\psi\rangle)$ is an eigenstate of $M$ with eigenvalue $1$ (just act on it with $M=U Z_1 U^\dagger$ to see ...
user avatar
1 vote
Accepted

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

Suppose you have some state $\newcommand{\ket}[1]{\lvert#1\rangle}\ket\psi$ (though note that you could make the identical argument using an arbitrary vector rather than a state), and you consider the ...
user avatar
  • 18.1k

Only top scored, non community-wiki answers of a minimum length are eligible