Tag Info

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,549

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,183
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 ...
• 38.8k
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,...
• 25.6k
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 ...
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 ...
• 23k
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,655
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 ...
• 59.4k
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 ...
• 59.4k
Accepted

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,436 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,716 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,... • 59.4k 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. • 38.8k 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, ... 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 ... • 4,987 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,716 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,202 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 ... • 23k 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.2k 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\...
• 59.4k
Accepted

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.2k
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$...
• 59.4k
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 ...
• 10.9k
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$, ...
• 59.4k
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,558
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 ...
• 59.4k
Accepted

Do all physical architectures for quantum computers use the same universal gate sets?

So any universal gate set can replicate any other, since both are universal, but different architectures generally have different physical gates. While Clifford+T is a universal gate set that is very ...
• 1,806
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 ...