25

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


18

You can build your gate with Operator and unitary function e.g: from qiskit import QuantumCircuit, QuantumRegister from qiskit.quantum_info.operators import Operator controls = QuantumRegister(2) circuit = QuantumCircuit(controls) cx = Operator([ [1, 0, 0, 0], [0, 0, 0, 1], [0, 0, 1, 0], [0, 1, 0, 0] ]) circuit.unitary(cx, [0, 1], label='cx'...


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


13

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


12

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


12

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


11

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


10

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


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

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


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

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

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


9

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


9

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


9

Any compilation/circuit optimization happens transparently by Qiskit. As a user you have control over what happens via the optimization_level argument passed to transpile(). Setting optimization level high (e.g. level 3) will do more circuit optimizations and setting it low will do little or no optimization (e.g. level 0). The two examples that you provide ...


8

Reformulating your question: How to perform Hamiltonian Simulation for a generic square matrix $A$? Quick answer: it is not possible. The goal of Hamiltonian Simulation (HS) is to find a quantum circuit (i.e. a succession of gates) that acts like $U(t) = e^{-iAt}$ on a quantum state. Here $U(t)$ needs to be unitary (because of the properties of quantum ...


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

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


8

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.


8

Here's the circuit for your specific case: I made it manually, by entering the matrix into Quirk, diagonalizing the matrix by adding operations, then simplifying the operations. It's not too hard to do by hand when all the operations are Clifford as in this case.


8

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


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


8

No this is not possible. One argument is the following: Toffoli + Hadamard are universal for quantum computation, so if you can make Toffoli from controlled-not then controlled-not + Hadamard would be universal. However, we know (Gottesman-Knill theorem) that the effects of controlled-not + Hadamard can be classically simulated, and so if we believe that ...


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

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


7

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


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

Take your vector $\frac{1}{\sqrt{5}}(0, 1, 1, 1, 1, 1)^T$ and five other arbitrary ones but at the same time these vectors have to be linearly independent. After that apply Gram-Schmidt process which produces orthonormal vectors. Put these vectors to a matrix and you will get a unitary matrix with the first column equal to $\frac{1}{\sqrt{5}}(0, 1, 1, 1, 1, ...


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