31 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 ...
JSdJ's user avatar
  • 5,449
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's user avatar
  • 24.8k
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 ...
Brian R. La Cour's user avatar
14 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 ...
forky40's user avatar
  • 6,728
13 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 ...
Adam Zalcman's user avatar
  • 22.3k
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 ...
Nikita Nemkov's user avatar
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 ...
DaftWullie's user avatar
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 ...
DaftWullie's user avatar
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 ...
Greg Kuperberg's user avatar
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 ...
Mithrandir24601's user avatar
  • 3,686
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 ...
rrtucci's user avatar
  • 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,...
DaftWullie's user avatar
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.
Craig Gidney's user avatar
  • 36.7k
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, ...
Johannes Jakob Meyer's user avatar
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 ...
Adrien Suau's user avatar
  • 4,927
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 ...
Mithrandir24601's user avatar
  • 3,686
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,...
Markus Heinrich's user avatar
9 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 ...
Adam Zalcman's user avatar
  • 22.3k
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 ...
Niel de Beaudrap's user avatar
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\...
DaftWullie's user avatar
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 ...
Niel de Beaudrap's user avatar
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$...
DaftWullie's user avatar
8 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 ...
Egretta.Thula's user avatar
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$, ...
DaftWullie's user avatar
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 ...
Matthew Stypulkoski's user avatar
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 ...
DaftWullie's user avatar
7 votes

What are magic states?

Consider a quantum computer that can: Prepare qubits in state $|0\rangle$ Apply unitary gates from the Clifford group Measure qubits in the $X$, $Y$, and $Z$ bases This seems ideal because: We know ...
user1271772 No more free time's user avatar
7 votes
Accepted

What is the purpose of gates with more than 2 inputs?

It's very similar to the same question for classical computation. You can express all algorithms that can be described with Boolean logic using only NOR or NAND logical gates, but you really don't ...
Mariia Mykhailova's user avatar
7 votes
Accepted

Prove that sets of gates $\{CNOT^a, H^b, T^c\}$ are not universal

First gate set: only has single qubit gates. The group of single qubit gates is closed under composition. E.g. you can't get to CNOT because it's not a single qubit gate. Second gate set: only has ...
Craig Gidney's user avatar
  • 36.7k
7 votes
Accepted

construction of Y gate from X,Z and H gates

First, you got a mistake there. The correct decomposition is $$X = HZH.$$ The way you find the decomposition is by understanding that $HZH$ performs the change of basis. The right-most $H$ brings a ...
MonteNero's user avatar
  • 2,481

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