14

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

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

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


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

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


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

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


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

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


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

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

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

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

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


3

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


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

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

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

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


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


1

Simply implement the gate $$ \left(\begin{array}{cc} 1 & 0 \\ 0 & e^{i\theta} \end{array}\right) $$ on the control qubit.


1

What would be the simplest thing that could be done to make it universal? See US Patent US9162881B2 "Physical realizations of a universal adiabatic quantum computer" or US Application US20150111754A1 "Universal adiabatic quantum computing with superconducting qubits" which is quoted here: Definition: Basis Throughout this specification and the appended ...


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