25

As per the linked question, the simplest solution is just to get the classical processor to perform such operations if possible. Of course, that may not be possible, so we want to create an adder. There are two types of single bit adder - the half-adder and the full adder. The half-adder takes the inputs $A$ and $B$ and outputs the 'sum' (XOR operation) $S =...


25

Quantum interference is the heart and soul of quantum computation. Whenever you have junk qubits they're going to prevent interference. This is actually a very simple but very important point. Let's say we have a function $f:\{0,1\}\to\{0,1\}$ which maps a single bit to a single bit. Say $f$ is a very simple function, like $f(x)=x$. Let's say we had a ...


24

The function $f$ is simply an arbitrary boolean function of a bit string: $f\colon \{0,1\}^n \to \{0,1\}$. For applications to breaking cryptography, such as [1], [2], or [3], this is not actually a ‘database lookup’, which would necessitate storing the entire database as a quantum circuit somehow, but rather a function such as \begin{equation*} x \...


19

The circuit depth is the length of the longest path from the input (or from a preparation) to the output (or a measurement gate), moving forward in time along qubit wires. The stopping points on the path are the gates, the allowed paths that must be considered can enter and exit those gates on any input / output, and the length is the number of ...


18

You won't find the barrier in quantum computing textbooks because it isn't a standard primitive of quantum information theory like unitary gates and quantum circuits. The barrier acts as a directive for circuit compilation to separate pieces of a circuit so that any optimizations or re-writes are constrained to only act between barriers (and if there are no ...


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


14

An approach for Hamiltonian simulation: Any Hermitian (Hamiltonian) matrix $H$ can be decomposed by the sum of Pauli products with real coefficients (see this thread). An example of 3 qubit Hamiltonian: $$H = 11 \sigma_z \otimes \sigma_z + 7 \sigma_z \otimes \sigma_x - 5\sigma_z \otimes \sigma_x \otimes \sigma_y$$ The final circuit for $e^{iHt}$ can be ...


13

The double lines are one common convention for classical bits in quantum circuit diagrams. In this case, they represent the bits arising from the measurements of the qubits msg and here. The controlled operations involving the classical bits are just operations which are performed if those classical bits happen to have the value 1, which is what the if ...


13

Entangling measurements are powerful. In fact, they are so powerful that universal quantum computation can be performed by sequences of entangling measurements only (i.e., without extra need for unitary gates or special input state preparations): Nielsen showed that universal quantum computation is possible given a quantum memory and the ability to perform ...


12

Here is how you might go about designing such a circuit.$\def\ket#1{\lvert#1\rangle}$ Suppose that you would like to produce the state $\ket{\psi} = \tfrac{1}{\sqrt 3} \bigl( \ket{00} + \ket{01} + \ket{10} \bigr)$. Note the normalisation of ${\small 1}/\small \sqrt 3$, which is necessary for $\ket{\psi}$ to be a unit vector. If we want to consider a ...


11

Break the problem in parts. Say we have already sent $\mid 00 \rangle$ to $\frac{1}{\sqrt{3}} \mid 00 \rangle + \frac{\sqrt{2}}{\sqrt{3}}\mid 01 \rangle$. We can send that to $\frac{1}{\sqrt{3}} \mid 00 \rangle + (\frac{1}{2} (1+i))\frac{\sqrt{2}}{\sqrt{3}}\mid 01 \rangle + (\frac{1}{2} (1-i))\frac{\sqrt{2}}{\sqrt{3}}\mid 10 \rangle$ by a $\sqrt{SWAP}$. ...


11

Edit — I've revised this answer to make some small improvements in the commands, to tidy up the commands for drawing the wires for instance, because it seemed worthwhile. Flattering as it is to have this answer be the accepted one for the time being, I think I should point out that the quantikz package (see Daftwullie's answer below) and the qpic ...


11

Consider the state $\frac{1}{2}(|00⟩ + |01⟩ + |10⟩ + |11⟩)$. This admits a factorisation $$\begin{align*}\frac{1}{2}(|00⟩ + |01⟩ + |10⟩ + |11⟩)&=\frac12\{|0\rangle\otimes(|0\rangle+|1\rangle)+|1\rangle\otimes(|0\rangle+|1\rangle)\}\\&=\frac12\{(|0\rangle+|1\rangle)\otimes(|0\rangle+|1\rangle)\}\\&=\left(\frac{|0\rangle+|1\rangle}{\sqrt2}\right)\...


11

The case of 1 qubit turns out to be pretty bad for understanding Grover's algorithm. There are several scenarios for the function you're looking at: Both inputs are solutions to $f(x) = 1$. The classical solution takes one function evaluation, so there is no speedup. Both inputs are not solutions. No matter how many iterations you do, Grover's algorithm is ...


10

I'll tell you how to create any two qubit pure state you might ever be interested in. Hopefully you can use it to generate the state you want. Using a single qubit rotation followed by a cnot, it is possible to create states of the form $$ \alpha \, |0\rangle \otimes |0\rangle + \beta \, |1\rangle \otimes |1\rangle .$$ Then you can apply an arbitrary ...


10

I will try to translate the Kim et. al. experiment from an optics description into a quantum information description. Here is the experimental setup as you find it in the linked wikipedia article: We associate the blue path with $|0\rangle$ and the red with $|1\rangle$. The double slit can be described by a Hadamard gate. The BBO corresponds to a CNOT-gate. ...


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

For me the problem with understanding quantum oracles was figuring out how they work if the input is in superposition. The answer is: build the oracle so that it is a unitary which does the right thing for inputs in each of the computational basis states, and it will do the right thing for the superposition due to linearity of the unitary transformation. I ...


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


9

You can't directly use a classical XOR gate inside a quantum circuit because the usual construction of such a gate is a classical construction - it won't preserve coherence. In other words, it will function just fine if you input a 0 or a 1 as each input, but it won't perform as you'd need it to if you supplied it with a superposition. Instead, you can ...


9

Yes. You have been given a factorization $QFT=U_1 \cdots U_n$ where each $U_i$ is an individual gate. $$ QFT^{-1} = U_n^{-1} \cdots U_1^{-1}\\ = U_n^{\dagger} \cdots U_1^{\dagger}\\ $$ A lot of the individual gates will have the property that $U_i = U_i^\dagger = U_i^{-1}$. These are the involutions like NOT, CNOT, etc. In those cases you are lucky and ...


9

Do you mean mapping the state $|0\rangle^{\otimes n} \to \dfrac{1}{\sqrt{2^n}}\sum_{i=0}^{2^n-1} |i\rangle $ ? If that is the case then you can just apply $H^{\otimes n}$ to the state $|0\rangle^{\otimes n}$. That is, you apply a Hadamard gate to each of the qubit. The reason for this is $H |0\rangle = \dfrac{|0\rangle + |1\rangle}{\sqrt{2}}$ and so \begin{...


9

Consider a quantum circuit on one qubit initialized in the state $|0\rangle$ and consisting of two Hadamard gates where we can insert a measurement between the Hadamards. The input state is $|0\rangle$, so the state after the first Hadamard gate is $$ H|0\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle) $$ which is an equal superposition of $|0\rangle$ and ...


8

Taking your comment to Kiro to its logical conclusion, the answer is 'yes'. The basic idea is to decompose the T gate 'magic' state $\tfrac{1}{\sqrt 2}\bigl(\lvert 0 \rangle + \mathrm{e}^{i \pi / 4} \lvert 1 \rangle \bigr)$ as a linear combination of stabiliser states. (If you do this for several magic states, this produces an exponentially large linear ...


8

You're correct, there is a bug in the algorithm described by the paper. D should be unconditionally decremented in each iteration, and the control (which I would instead call the accumulator... except it looks like it is actually intended to control it?) should be toggled if D=0. The author has made the mistake of conditioning the decrement on the ...


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


8

Yes, that notation means the Hadamard on the second qubit depends on the first qubit and the Hadamard on the third qubit depends on the first qubit. The gates aren't connected to each other in any way.


8

A universal method to decompose 2-qubit unitaries into primitive gates is sometimes referred to as "Krauss-Cirac decomposition". Here are several sources: Optimal Quantum Circuits for General Two-Qubit Gates by Vatan and Williams, Optimal Creation of Entanglement Using a Two–Qubit Gate by Kraus and Cirac. “Explorations in Quantum Computing” by Williams, ...


7

$$ \newcommand{\bra}[1]{\left<#1\right|}\newcommand{\ket}[1]{\left|#1\right>}\newcommand{\bk}[2]{\left<#1\middle|#2\right>}\newcommand{\bke}[3]{\left<#1\middle|#2\middle|#3\right>}\newcommand{\proj}[1]{\left|#1\right\rangle\left\langle#1\right|} $$ Much of the functionality here is the same as the Bernstien-Vazirani algorithm, if that helps....


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