# Tag Info

15

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

10

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

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

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

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

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

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

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

8

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

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.

6

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

6

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

6

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

5

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

5

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

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

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

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

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

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.

4

Suppose that an exact synthesis was possible for your provided unitary (the number of theoretic restriction on the entries) and so the algorithms described in the question gave you a sequence of Clifford+T gates that implemented that unitary. As stated in the Giles-Selinger paper, you get a sequence that is very far from optimal. So at this point you have ...

4

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

3

Nielsen and Chuang, pg 191 of the 10th anniversary edition: We have just shown that an arbitrary unitary matrix on a $d$-dimensional Hilbert space may be written as a product of two-level unitary matrices. Now we show that single qubit and CNOT gates together can be used to implement an arbitrary two-level unitary operation on the state space of $n$ ...

3

This paper gives a fairly complete answer to the question "given oracle access to U, implement the inverse of U". https://arxiv.org/abs/1810.06944 They give a protocol which implements U inverse with a number of queries that's linear in the dimension of U and show that this is essentially optimal. This seems to be fairly closely related to your question....

3

Talking about efficiency here isn't exactly a fair question: as you change n, the number of qubits in the Fourier transfer, you're changing the gate that you're talking about using (because the smallest phase will be something like controlled-$Z(\pi/2^n)$). After all, if I can do controlled-$Z$ when I have two qubits, why would I suddenly lose the ability to ...

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