# Tag Info

13

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 ...

9

Here is a SQRT(SWAP) construction which only requires CNOTs in one direction, Hadamards, S gates ($Z^{\frac{1}{2}}$), inverse S gates ($Z^{-\frac{1}{2}}$), T gates ($Z^{\frac{1}{4}}$) and inverse T gates ($Z^{-\frac{1}{4}}$): You should be able to encode it directly into the composer.

9

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 ...

9

One way order to perform Z rotations by arbitrary angles is to approximate them with a sequence of Hadamard and T gates. If you need the approximation to have maximum error $\epsilon$, there are known constructions that do this using roughly $3 \lg \frac{1}{\epsilon}$ T gates. See "Optimal ancilla-free Clifford+T approximation of z-rotations" by Ross et al. ...

9

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 ...

9

is the decomposition (I took this from google images, originally on this website.) In order to understand how to decompose it, we can look at it's base structure. The idea is that we combine gates that cancel out, but put CNOT gates in between such that if the specific NOT is executed, the gates don't cancel. This is how generic controlled-U gates are ...

8

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 ...

8

Below is a recent paper by Gilyén et al on doing "quantum matrix arithmetics", allowing to implement linear combinations of unitary operators. They consider the general case where the linear combination in itself might not be unitary. Since the linear combination in your case is unitary, maybe there's a more efficient way. [1]: Gilyén, András, et al. "...

8

The key is that you don't actually construct a matrix. Yes, if you wanted to simulate a quantum computation on a classical computer, one method is to build the corresponding unitary matrix, and this is essentially why (unless there's special structure) it's impossible to efficiently perform a classical simulation of quantum computation. However, think on ...

7

For a presentation from first principles, I like Ryan O'Donnell's answer. But for a slightly higher-level algebraic treatment, here's how I would do it. The main feature of a controlled-$U$ operation, for any unitary $U$, is that it (coherently) performs an operation on some qubits depending on the value of some single qubit. The way that we can write this ...

7

You have picked two particularly simple matrices to implement. The first operation (G) is just the square root of X gate (up to global phase): In your gate set, this is $R_X(\pi/2)$. The second operation (W) is a Hadamard matrix in the middle 2x2 block of an otherwise-identity matrix. Anytime you see this 2x2-in-the-middle pattern you should think "...

6

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 ...

6

As pointed out by @Nelimee, this question is essentially answered in this question, even if that question seems more specific. However, for the sake of completeness... (Note that I make no claims about minimality of construction with respect to, for example, number of controlled-not gates.) Let's start with a unitary matrix for the square root of SWAP: $$\... 6 I guess what you're looking for is the following circuit. Here, b_1,b_2,b_3,b_4 \in \{0,1\}, and \oplus is addition modulo 2. Here, the fifth qubit is used as an auxiliary, or ancilla qubit. It starts at |0\rangle and ends in |0\rangle when the circuit is applied. Let me elaborate on how this circuit works. The idea is to first of all check ... 6 Let's start with some general theory. If you have a normal matrix A (of which unitaries are a subset), you can define any function of that matrix f(A). For example, A^{1/2} or A^{\pi}. The most natural way to do this is via the spectral decomposition: if \{\lambda_i\} are the eigenvalues of A and U is the matrix that diagonalises A:$$ UAU^\...

6

You also have this one with V the square root of NOT gate: If you have as control qubits : (0,0) : do nothing; (0,1) : apply V and its conjugate which is identity; (1,0) : same but inversed; (1,1) : apply V twice which correspond to your NOT gate.

6

Let $g_1 \cdots g_M$ be the basic gates that you are allowed to use. For the purposes of this $\operatorname{CNOT}_{12}$ and $\operatorname{CNOT}_{13}$ etc are treated as separate. So $M$ is polynomially dependent on $n$, the number of qubits. The precise dependence involves details of the sorts of gates you use and how $k$-local they are. For example, if ...

6

Exact decomposition for your particular gate set Given the range of $R_x$ gates available to you together with arbitrary $R_z$ gates, you should be able to find an easy decomposition of arbitrary $R_y$ gates (i.e. as a product of three of your elementary gates). Then using simple techniques — similar to the exercises of Chapter 4 in Nielsen & ...

6

This is a good question; it's one that textbooks seem to sneak around. I reached this exact question when preparing a quantum computing lecture a couple days ago. As far as I can tell, there's no way of getting the desired 8x8 matrix using the Kronecker product $\otimes$ notation for matrices. All you can really say is: Your operation of applying CNOT to ...

6

What you are trying to do is called Hamiltonian Simulation. If your exponential can be split in a sum of unitary matrices, @smapers' answer guide you to a good algorithm: the Linear Combination of Unitary (LCU) algorithm. In addition to the paper linked by @smapers, here are some other papers/videos explaining LCU: Maybe the first paper to present LCU: ...

6

The whole point is that CNOT cannot be written in the form $A\otimes B$. This is absolutely essential because if we only ever had operators of the form $A\otimes B$, states of the form $|\psi\rangle\otimes|\phi\rangle$ would always remain separable. There's be no entanglement, and all quantum circuits would be easy to simulate on a classical computer. As ...

5

You can make controlled $R_y$ gates from cnots and $R_y$ rotations, so they can be be done on any pair of qubits that allows a cnot. Two examples of controlled-Ys are shown in the image below. They are on the same circuit, one after the other. The first has qubit 1 as control and qubit 0 as target, which is easy because the cnots can be directly ...

5

You get two decompositions for your matrix (let's call it $A$) because you are using two different operatorial bases. In the first case you are considering the matrix as acting in a space of dimension $3\times 2$, that is, using the operatorial basis $\{\lambda_i\sigma_j\}_{ij}\equiv\{\lambda_i\otimes\sigma_j\}_{ij}$. In other words, you are computing the ...

5

(EDIT: Improved to 14 CNOTs.) It can be done with 14 CNOTs, plus 15 single-qubit Z rotations, and no auxiliary qubits. The corresponding circuit is where the $\fbox{$\pm$}$ gates are rotations $$R_z(\pm\pi/16)\propto \left(\begin{matrix}1\\&e^{\pm i\pi/8} \end{matrix}\right)$$ Derivation: Using the procedure described in https://arxiv.org/abs/...

5

Here is a CCCZ construction that uses 29 gates: If you're allowed to use measurement and classical feedforward, the gate count can be reduced to 25: (The Hadamard gates can be replaced with square roots of Y if needed to meet the gate set constraint.) And if you allow me to perform Controlled-S gates and Controlled-sqrt(X) gates and perform X basis ...

5

Math: If you are familiar with tensor products, observe that $I \otimes X$ gives the desired matrix. Showing the steps of this computation, $I \otimes X = \begin{pmatrix}1 &0\\0 & 1 \end{pmatrix} \otimes \begin{pmatrix}0 &1\\1 & 0 \end{pmatrix} = \begin{pmatrix}1\begin{pmatrix}0 &1\\1 & 0 \end{pmatrix} & 0 \begin{pmatrix}0 &... 5 By giving U as that sequence you have reduced the problem to controlled SWAPs, cXs, cYs and cZs already. The single qubit gates you already know how to make controlled. You can reduce further to controlled SWAPs and cXs by putting in the appropriate$U$such that$UXU^\dagger=Y$or$Z\$. That gets rid of dealing with the controlled cYs and cZs separately. ...

4

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 ...

4

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 ...

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