9

By definition, conjugation by a Clifford gate preserves the Pauli group $G = \langle X, Y, Z\rangle$. It is easy to check that $SXS^\dagger = Y, SYS^\dagger = -X$ and $SZS^\dagger = Z$. Since $G = \langle -X, Y, Z\rangle$ we see that $S$ is Clifford. On the other hand, $TXT^\dagger = \begin{pmatrix} & e^{-i\pi/4}\\ e^{i\pi/4}&\end{pmatrix} \notin G$, ...


8

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 significantly more spacetime volume than Clifford gates. For reference, see the introduction sections here and here. The natural expectation would be that no quantum ...


7

Short answer: Yes, this should be possible. However, the details have to be filled out. The key is to relate this to magic monotones. There has been some development since the 2016 Bravyi-Gosset paper. I think one can use an argumentation based on stabiliser / Clifford extent and the results in the BBCCGH paper from 2019. Similarly, one can also argue for ...


7

Geometrically: For a single qubit, we have the Bloch sphere and the stabiliser states span an octahedron inside it. Unitaries act in the adjoint representation as $SO(3)$, i.e. they induce rotations of the Bloch sphere. It is easy to see, that only rotations about the $X,Y,Z$ axis with angles $\theta=\pi/2,\pi,3\pi/2,2\pi$ preserve the octahedron. This ...


7

Here's a simple strategy based on the idea that Clifford operations conjugate Pauli products into other Pauli products. If $U$ is a Clifford operation, then $U P U^\dagger$ (where $P$ is a Pauli operation on one of the qubits) will be a matrix equivalent to a product of Pauli operations. If you check this for each $X_q$ and $Z_q$ for each qubit $q$, the ...


7

As a general rule, you wouldn't bother constructing this: it is just a global phase that has no observable consequence. If you really insist on doing this, introduce an ancilla qubit in the $|1\rangle$ state and apply a $Z$ gate to it. PS "inverse identity gate" is a really bad name for it. The identity operation is its own inverse.


7

Sometimes, there is a bit of confusion around the Clifford group in the field ... and it's a matter of definition. A lot of people define the Clifford group $\mathrm{Cl}_n(p)$ of $n$ qudits of prime dimension $p$ as the unitary normaliser of the generalised Pauli group (e.g. Gottesman, Nielsen & Chuang). As such, it is clearly not a finite group as the ...


6

The quaternions are represented faithfully in two dimensions by the unit matrix and the Pauli matrices multiplied by the imaginary unit: $i = \sqrt{-1} X$, $j = \sqrt{-1} Y$ and $k = \sqrt{-1} Z$ respectively, thus you only need to write $H$ and $P$ the linear combinations: $H = -\frac{\sqrt{-1} }{\sqrt{2}}(i+k)$ and $P = \frac{1+\sqrt{-1}}{2}(1-k)$ However,...


6

Following Dehaene and de Moor (Theorem 6 in particular), every Clifford unitary can be represented (up to a global scalar factor) by an expression of the form $$ U = 2^{-k/2} \!\!\!\!\!\!\sum_{\substack{x_r,x_c \in \{0,1\}^k \\ x_b \in \{0,1\}^{n-k}}}\!\!\!\!\! i^{p(x_b,x_c,x_r)} (-1)^{q(x_b,x_c,x_r)} \bigl\lvert T_1[x_r;x_b] \bigr\rangle\!\bigl\langle T_2[...


5

The terms $II$ and $ZZ$ do not uniquely specify the state $|11\rangle$ because you could equally have the state $|00\rangle$. Indeed, you should not include the identity term in your stabilizer. Thus, you need to add a second term, which could be either $-ZI$ or $-IZ$. Either way, you can easily see how to make a product $-ZI$ out of your stabilizers.


5

No. There always exists a unique unitary $U$ such that $CT=TU$. Namely, $U = T^\dagger C T$. The question is whether $U$ is Clifford. It turns out that this is not guaranteed. For a simple counterexample take Hadamard for $C$. Then $$ U=T^\dagger H T = \frac{1}{\sqrt{2}}\begin{bmatrix} 1 & e^{i\pi/4} \\ e^{-i\pi/4} & -1 \end{bmatrix} $$ is not ...


5

The orthonormal basis $|j\rangle$ of the $d$ dimensional finite Hilbert space corresponds to a configuration space of equally spaced clockwise ordered $d$ points on a circle $S^1$ or equivalently, the vertices of a $d$-dimensional regular polygon. One may think of a point as a discrete location of a particle, then the shift operator $X$ shifts the particle ...


5

The shift operator takes his name from the fact that it shifts the position of its input, as in, it sends $1\to2$, $2\to3$ etc, with the last computational basis element being sent back to the first one: $d\to 1$ (or the same thing starting with $0$, depending on notation). As per the "boost" operator $Z$, I have usually seen those referred to as "clock ...


5

The difference in definitions is from either taking the unitary group or the projective unitary group. That accounts for the constant prefactors of $\pm i$ that are missing. In lieu of a tikz commutative diagram \begin{align} <X,Y,Z> & \hookrightarrow & U(2)\\ \downarrow & & \downarrow\\ <[X],[Z]> & \hookrightarrow & PU(...


4

Note that the second definition actually doesn't make more sense in the context of the stabiliser formalism, as neither of $\pm i Y$ have a +1 eigenspace. That means that you can only describe states which are stabilised by operators with two or more factors of $\pm i Y$. This is only enough to simulate real stabiliser circuits, which is what you're noticing....


4

There is a very closely related representation of the tableau representation of Aaronson (and Gottesman), which works not only for qubits but for qudits of arbitrary finite dimension, which works particularly well for purely Clifford circuits (i.e. at most one terminal measurement). In this alternative representation, one has tableaus describing how ...


3

One way that you might do it is as follows. Consider the unitary sequence $V=HTHT$. Because it's unitary, we can write it in the form $$ V=e^{i\gamma}e^{-i\theta\vec{n}\cdot\vec{\sigma}}=e^{i\gamma}(\cos\theta I-i\sin\theta \ \vec{n}\cdot\vec{\sigma}) $$ where $\vec{n}\cdot\vec{n}=1$. If you work through the details, you'll find that $$ \cos\theta=\cos^2\...


3

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 either, since any Clifford oracle accepts 0%, 50%, or 100% of all inputs which makes search trivial.


3

You might be interested in controlled version of $-I$. Despite the fact that you can neglect global phase in case of non-controlled gates, you cannot do so in case of controlled version. The controled gate $-I$ is described by matrix \begin{pmatrix} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & -1 & 0\\ 0 & 0 & 0 & -...


3

Yes, absolutely. That's very much the root of the whole thing. You start with a state from a particular class: a stabilizer state, i.e. one which can be described by a bunch of projectors $(I+K)/2$, where $K$ is from the Pauli Group. To determine how the state evolves under the action of the circuit, you only need to know how the circuit acts on the ...


2

In the surface code there are two major costs to T gates: the spacetime cost and the reaction time cost. The spacetime cost is due to the need to perform magic state distillation of a T state for each T gate, which takes hundreds of operations. A T gate factory producing a T state every hundred microseconds can easily monopolize a hundred thousand qubits. ...


2

I have not read the full details of the paper, but have attempted to skim over the most relevant bits to the question (i.e. I could easily have missed something). As I read the paper, they are doing some calculation with a fixed size of input, and they repeat it many times (see equation 58). They ask how many times do you have to repeat it to get the same ...


2

To draw out Aaronson and Gottesman's techniques a bit more explicitly: you can set up each stabilizer as a bit string of length $2N$ (for $N$ qubits). The first $N$ bits specify the locations of Z operators, and the second set of $N$ specify the locations of $X$ operators (so, $X_1Z_2$ for $N=2$ is 0110). For your circuit on four qubits, the transformation ...


2

The circuit is a Hadamard + a Controlled - Hadamard gate. Note that $ S $ gate is $ P $ gate in your notation.


2

No, you don't need ancillae. Ancilla qubits can be extremely helpful, but they are not necessary. For example, in Nielsen and Chuang this is proven by giving an explicit construction. Also, there's no restriction that the unitary has to be from the special unitary group. Any unitary operation can be approximated to arbitrarily good accuracy using Clifford+T.


2

The states reachable from $|0\rangle$ using Clifford gates are precisely the six eigenstates of the single-qubit Pauli operators, i.e. $$\mathcal{S} = \{|0\rangle, |1\rangle, |+\rangle, |-\rangle, |{+i}\rangle,|{-i}\rangle\}\tag1$$ which are also known as the single-qubit stabilizer states. Remark on generators It is easy to express Pauli operators $X$, $Y$ ...


2

Liu and Winter (http://arxiv.org/abs/2010.13817) have shown that any "reasonable" magic monotone is asymptotically bounded by $n$. Moreover, Haar-random pure states cluster around that value (deviation is exponentially suppressed in $n$). By a standard argument (as in Beverland et al.), $\Omega(n)$ magic implies that we need $\Omega(n)$ copies of ...


2

I wonder if there are explicit examples where the T-count scales stronger with n. [...] maybe superlinear or even exponential. Here's an existence proof of an $n$ qubit magic state with a T count of $\Theta(2^{n/4})$, based on caching QROM reads. It takes $\Theta(2^{n/4})$ T gates to prepare the cached-QROM state, and also you can consume the cached-QROM ...


1

Assuming the encoder itself doesn't have to be fault tolerant, you can do the proof constructively. Prepare the code space by projecting each of the stabilizers into the +1 eigenstate. For each stabilizer $S$: Measure $S$. If you're in the -1 eigenspace of $S$, apply Pauli gates to flip the stabilizer (but not other stabilizers). E.g. stim can compute ...


1

I'll denote $x=x_1\dots x_n \in \{0,1\}^n$ as a vector containing binary values. Certainly you can prepare $|x\rangle = X^{x_1} \otimes \cdots \otimes X^{x_n} |0\dots 0\rangle$ easily, and it turns out that a quantum circuit trying to classify $|x\rangle$ is also generally classically simulable since its entirely linear in elements of $x$. For completeness I'...


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