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

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

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

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

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

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

7

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

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

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

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

5

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

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.

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

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

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(... 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 ... 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 ... 2 You do not even need Z and X. \rm{CNOT}, H, and T=\pi/8 are enough. 1) H and T are enough to make any possible unitary transformation on one qubit. 2) Adding \rm{CNOT}, you can synthesize a general unitary transformation to within any error \epsilon>0 using only \mathcal{O}(\log^2(1/\epsilon)) gates.. If you wish for the error to ... 2 In the accepted answer, it is said that XX couplers are "necessary". However YY couplers would also do the job. This is because of te YY gadget explained in section VI of this paper. Actually even the original paper given in the accepted answer, says that XZ would also be good enough (not just XX). For that reason, YZ should also be good enough, although ... 2 I found out the number of ancillas is minimum n-2. I found this line in the Qiskit source code of mct: if len(ancillary_qubits) < len(control_qubits) - 2: raise AquaError('Insufficient number of ancillary qubits.') 2 You might like to look up about quantum cellular automata. These are systems where you can repeatedly apply the same global unitary operation to generate the circuit that you want. The circuit is specified by the initial (product) state that is operated on. In that sense, you achieve the inverse using the same sequence of unitaries, just by changing the ... 2 Here's a silly method that works if you know y, you know the probability of measuring y, and you can efficiently generate arbitrary-size superpositions of the form$$\frac{1}{\sqrt{N}}\sum_{b < N}\vert b\rangle.$$To do this, use a Grover-like search: You need two circuits U_y and U_0, with the following action:$$U_y\vert x\rangle \vert \psi\...

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