34
votes
Accepted
What are magic states?
Magic states are certain states that have very nice properties with respect to fault-tolerant quantum computation.
In the vast landscape of quantum gates, there is a crude but useful distinction to be ...
- 5,749
18
votes
What are magic states?
In addition to the accepted answer and @user1271772's examples, here is a circuit primitive referred to explicitly as a "T-gate gadget" in [1] (originally appearing in [2]):
where ...
- 7,721
18
votes
Accepted
Does the Quantum Fourier Transform require universality?
Yes, the QFT requires universality. No, there isn't a non-universal gate set that implements the QFT. Just having the QFT as an operation is already computationally universal, because it can generate ...
- 42.1k
16
votes
Accepted
Given a decomposition for a unitary $U$, how do you decompose the corresponding controlled unitary gate $C(U)$?
The question may not be entirely well-defined, in the sense that to ask for a way to compute $C(U)$ from a decomposition of $U$ you need to specify the set of gates that you are willing to use.
Indeed,...
glS♦
- 26.9k
16
votes
Accepted
Does anyone know the list of all known universal sets of quantum gates?
Too many to list
There exist uncountably many universal sets of gates. We will sketch a proof of this fact by outlining a construction of an uncountable, though by no means exhaustive, family of such ...
- 24.9k
14
votes
Accepted
What is the mathematical justification for the "universality" of the universal set of quantum gates (CNOT, H, Z, X and π/8)?
The answer you mention references Michael Nielsen and Isaac Chuang's book, Quantum Computation and Quantum Information (Cambridge University Press), which does contain a proof of the universality of ...
- 506
13
votes
Accepted
Minimum number of 2 qubit gates to build any unitary
Theoretical lower bound
In contrast to the answer by Bertrand, I will assume that along with a $CNOT$ gate we have arbitrary single-qubit unitaries on our disposal. In this case, one can derive the ...
- 1,705
12
votes
Accepted
Is the Solovay-Kitaev theorem relevant for modern hardware?
I think you'll find that most hardware, at the hardware level, gives you arbitrary single qubit rotations. So, in that sense, it is true that Solovay-Kitaev is not directly applicable to current ...
- 61.8k
11
votes
Accepted
How to prove/disprove universality for a set of gates?
Universality can be a very subtle thing which is quite tricky to prove. There are usually two options for proving it:
show directly, using your chosen gates, how to construct any arbitrary unitary of ...
- 61.8k
11
votes
Accepted
How to intuitively understand why $T$ gate can't be implemented transversally?
TL;DR: It is not true that $T$ gate can't be implemented transversally. However, universal gatesets, such as $\text{Clifford}{+}T$, cannot be implemented transversally by Eastin-Knill theorem. The ...
- 24.9k
10
votes
Accepted
Explicit Conversion Between Universal Gate Sets
To fix what we are talking about, I think you mean
$$ H = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} \quad
S = \begin{pmatrix} 1 & 0 \\ 0 & i \end{pmatrix} \quad
...
- 1,446
10
votes
Accepted
How does approximating gates via universal gates scale with the length of the computation?
Throughout this answer, the norm of a matrix $A$, $\left\lVert A\right\rVert$ will be taken to be the spectral norm of $A$ (that is, the largest singular value of $A$). The solovay-Kitaev theorem ...
- 3,766
10
votes
Accepted
Shortest sequence of universal quantum gates that correspond to a given unitary
Getting an optimal decomposition is definitely an open problem. (And, of course, the decomposition is intractable, $\exp(n)$ gates for large $n$.) A "simpler" question you might ask first is what is ...
- 679
10
votes
Accepted
Why is the Toffoli gate not sufficient for universal quantum computation?
The Toffoli gate is just a permutation. If you start in a known basis state, application of a Toffoli just changes it into another basis state, one that you can easily calculate classically (after all,...
- 61.8k
10
votes
Accepted
Can a Toffoli gate be implemented using Fredkin gates?
It's not possible to implement a Toffoli using only Fredkin gates, because Fredkin gates preserve the number of 1s in the state while Toffolis do not.
- 42.1k
10
votes
Accepted
How can I see, without math, the action of a gate in matrix form?
Besides the already given answers note that there is indeed some "mental gymnastics" involved here. As soon as you're getting more acquainted with quantum computing, you know some of your usual gates, ...
10
votes
Accepted
Is SO(2) with any entangling gate universal?
No. With the conventional notation of the Pauli basis, $SO(2) \cong U(1)$ rotations just constitute rotations around $Y$, i.e., these gates are parameterized by the set
$\{e^{i \theta Y} : \theta \in [...
- 541
9
votes
Sampling random circuits vs Solovay-Kitaev compiler
The Solovay-Kitaev algorithm is not practical. It is very useful theoretically because it proves that once you have a "dense" set of quantum gates (i.e. a set with which you can approximate any other ...
- 5,112
9
votes
Accepted
How are gates implemented in a continuous-variable quantum computer?
Taking an $n$-mode simple harmonic oscillator (SHO) in a (Fock) space $\mathcal F = \bigotimes_k\mathcal H_k$, where $\mathcal H_k$ is the Hilbert space of a SHO on mode $k$.
This gives the usual ...
- 3,766
9
votes
Accepted
How efficient is Qiskit's unitary decomposition?
For 2x2 unitary, it is just a U3-gate.
For 4x4 unitary, TwoQubitBasisDecomposer is used. TwoQubitBasisDecomposer implements KAK ...
- 11.8k
9
votes
Accepted
Prove that adding any non Clifford gate to the Clifford group yields a universal gate set
There is at least one other way to prove this I'm aware of. The argument uses the concept of a unitary 2-design and how this restricts the representation theory of a group.
To avoid pathological cases,...
- 5,447
8
votes
Accepted
Quantum XNOR Gate Construction
Any classical one-bit function $f:x\mapsto y$ where $x\in\{0,1\}^n$ is an $n$-bit input and $y\in\{0,1\}$ is an $n$-bit output can be written as a reversible computation,
$$
f_r:(x,y)\mapsto (x,y\...
- 61.8k
8
votes
Accepted
Quantum XOR Linked List Construction
Caveat. I can't be absolutely certain that no-one has contemplated a quantum XOR list before — but I can be pretty confident. On the theory side, the idea of data structures as granular as ...
- 12.4k
8
votes
Accepted
What are the fundamental differences between trapped ion quantum computers and other architectures?
Disclosure: while I am not an experimental physicist, I am part of the NQIT project, which is aiming to develop quantum hardware which is suitable to realise scalable quantum computers. The ...
- 12.4k
8
votes
Accepted
How do I create an inverse identity gate?
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$...
- 61.8k
8
votes
Accepted
Why is the angle of $R_z(\frac\pi4) R_x(\frac\pi4)$ an irrational multiple of $\pi$
Section 3 in the paper "On Universal and Fault-Tolerant Quantum Computing" by Boykin et al contains the detailed proof of this fact.
The proof goes as follows:
$\exp(-i\frac{\pi}{8}Z)\exp(-...
- 11.8k
8
votes
Accepted
Can W gate be written only using H,T?
Try the sequence:
$$
HT^6HT^2H.
$$
What was my thinking? I'm used to doing a transformation that looks something like
$$
S^\dagger H S.
$$
The action is the $S$ is to preserve the $Z$ term inside $H$, ...
- 61.8k
7
votes
Accepted
What does a quantum circuit look like after qiskit.compile() has been applied?
The function that handles this is transpile(), which could be found in qiskit.compiler. When you call ...
- 1,568
7
votes
Given a decomposition for a unitary $U$, how do you decompose the corresponding controlled unitary gate $C(U)$?
Although this might not answer your question completely, I think it might provide some direction of thinking. Here are two important facts:
Any unitary $2^{n}\times 2^{n}$ matrix $M$, can be realized ...
- 17.8k
7
votes
Accepted
Why is Deutsch's gate universal?
I have thoughts on a couple of different approaches, although I'm sure there'll be simpler options.
Firstly, imagine you start from a two-qubit state $|00\rangle$, and apply an $R_x$ rotation with an ...
- 61.8k
Only top scored, non community-wiki answers of a minimum length are eligible