16

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, it is a known result that any $n$-qubit gate can be exactly decomposed using $\text{CNOT}$ and single-qubit operations, so that a naive answer to the question ...


16

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 made between Clifford gates and all other gates (also referred to as the inspired non-Clifford gates). The set of Clifford gates is in technical terms the ...


11

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 these gates. (In my 2000 edition, this can be found on p. 194.) The key insight is that the $T$ gate (or $\pi/8$ gate), together with the $H$ gate, generates ...


10

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 states that approximating a gate to within an error $\epsilon$ requires $$\mathcal O\left(\log^c\frac 1\epsilon\right)$$ gates, for $c<4$ in any fixed number of ...


10

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 the shortest sequence of cnots and single qubit rotations by any angle, (what IBM, Rigetti, and soon Google currently offer, this universal basis of gates can ...


10

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, including the $\mathsf{SWAP}$ gate that appears in your question: \begin{align} \mathsf{SWAP} = \begin{bmatrix} 1 &0 &0 &0 \\ 0 &0 &1 &...


9

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 annihilation operator $a_k$, which act on a number state as $a_k\left|n\right> = \sqrt n\left|n-1\right>$ for $n\geq 1$ and $a_k\left|0\right> = 0$ and ...


9

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 arbitrary size (there’s no constraint on the size of the construction, just that it can be done) to arbitrary accuracy (on some non-trivial sub space of the ...


9

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, it’s a decision based on looking at 3 bit values). Repeating that doesn’t change anything. To make it universal, you need to add something like Hadamard ...


8

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\oplus f(x)) $$ (Note that any function of $m$ outputs can be written as just $m$ separate 1-bit functions.) A quantum gate implementing this is basically just the ...


8

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 quantum gate) you can approximate up to an arbitrary precision and quickly any quantum gate. In practice, the Solovay-Kitaev works as follow: Fill the space ...


7

The function that handles this is transpile(), which could be found in qiskit.compiler. When you call transpile(circuit, backend) it goes through the compilation process for the input circuit based on the backend you provide. It returns a new circuit that will be valid to run on the provided backend. You can then view this new circuit just like you would ...


7

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 linked lists (of any description) is pretty low-level, and to my knowledge is not really the subject of research; and people working on architectures only dream of ...


7

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 T = \begin{pmatrix} 1 & 0 \\ 0 & \exp(i\pi/4) \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & \frac{1+i}{\sqrt{2}} \end{pmatrix}.$$ If these are ...


7

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 architecture that we're investing most heavily in is optically linked ion traps. Ions represent some of the physically best understood systems to experimental and ...


7

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.


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

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 sets. First, recall (e.g. from sections 4.5.2 and 4.5.3 of Nielsen & Chuang) that if $\mathcal{A}$ is a set of single-qubit gates that is universal for $SU(...


6

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 on a quantum computer with $n$-quantum bits by a finite sequence of controlled-not and single qubit gates1. Suppose $U$ is a unitary $2\times 2$ matrix ...


6

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 nice to think about theoretically, it isn't generally close to the one used in the lab. In most experimental setups, the physical level universal gate set used ...


5

XX couplers are necessary to make an quantum annealing universal. https://arxiv.org/abs/0704.1287 As for fabricating them, I’m not too familiar with the hardware issues. Perhaps someone else can comment on that.


5

What does a truth table for a QRCA look like? You don't want to know. It will be a gigantic complicated table that provides no insight whatsoever. At the very least you need to use boolean algebra instead of a table, but even that will be cumbersome and will require many intermediate values that ultimately are just a less-visual way of describing an ...


5

an arbitrary single qubit rotation and a CNOT comprises a universal gate set. Is this true? Yes. If you want to understand why, don't go with any answers about finite gate sets such as CNOT, H, T because the proof of those usually relies on the proof of the set you've stated (so the whole thing becomes horribly circular). Instead, you have to make some of ...


5

Toffoli and Hadamard are computationally universal -- that is, they can be used to carry out any quantum computation. However, they do so by implementing quantum gates in an encoded way. Indeed, this is necessary since both Toffoli and Hadamard have only real entries, so there is no way to obtain quantum gates with complex entries, unless one uses some ...


5

The quantum circuit model is one of the possible models for quantum computation. It is the most studied, because it is quite practical. Back to the origins, you can look at papers by David Deutsch, like: Quantum computational networks Proc. R. Soc. Lond. A 425, 73-90 (1989) For a slow start, I suggest to read Nielsen and Chuang's book and maybe Scott ...


5

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 application of the $S$ gate is conditioned on measuring a "1" on the ancilla. The way this works is, for $|A\rangle = \frac{1}{\sqrt{2}} (|0\rangle + e^{i\pi/...


4

You can prove that one gate set is universal by showing how to construct another universal gate set out of it. For example, we know that {H, T, cNOT} is universal, so can you find a way of making cNOT out of {H, T, CPHASE}? (Hint: Yes) On the other hand, the best way to prove that a gate set is not universal is to show that you can simulate the evolution of ...


4

There is no "standard" method to implement XNOR, but it can be logically obtained by attaching a NOT gate (often called an X gate in quantum computing) to a logical XOR (which you know is implemented using CNOT). The X gate is applied to the target qubit of the CNOT. To answer your question more directly, there is no standard "quantum gate" that is ...


4

In your question, you don't define $P(\theta)$ or $R_z(\theta)$. I'm going to assume: $$ P(\theta)=\left(\begin{array}{cc} 1 & 0 \\ 0 & e^{i\theta} \end{array}\right)\qquad R_z(\theta)=\left(\begin{array}e^{-i\theta} & 0 \\ 0 & e^{i\theta} \end{array}\right). $$ In this case, you simply have that $$ R_z(\theta)=P(2\theta)e^{-i\theta}\equiv P(...


4

The quantum XNOR is not a CCNOT. CCNOT would take 3 bits as input, whereas XOR, XNOR, and CNOT take in only 2 bits or qubits as input. The reason why we say the XOR can be thought of as a CNOT is explained here, and the same reasoning can be used to construct the (2 qubit) XNOR.


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