Tag Info

A first remark This same phenomenon of 'control' qubits changing states in some circumstances also occurs with controlled-NOT gates; in fact, this is the entire basis of eigenvalue estimation. So not only is it possible, it is an important fact about quantum computation that it is possible. It even has a name: a "phase kick", in which the control qubits (or ...

The phase kickback trick appears in this paper: Richard Cleve, Artur Ekert, Chiara Macchiavello, Michele Mosca. Quantum Algorithms Revisited. Proceedings of the Royal Society of London A, 454(1969): 339-354, 1998. The authors credit Alain Tapp for independently discovering the same improvement to Deutsch's algorithm that results from using this trick. (...

Imagine you have an eigenvector $|u\rangle$ of $U$. If you have a state such as $|1\rangle|u\rangle$ and you apply controlled-$U$ to it, you get out $e^{i\phi}|1\rangle|u\rangle$. The phase isn't attached to a specific register, it's just an overall multiplicative factor. Now let's use a superposition on the first register: $$ (|0\rangle+|1\rangle)|u\rangle\...

Phase estimation is the process by which you are given a controlled-$U$ unitary, and a state that you are promised is an eigenvector of $U$ with eigenvalue $e^{2\pi ix/2^t}$, then you can use a $t$-qubit register to affect the change $$ |0\rangle^{\otimes t}|u\rangle\mapsto|y\rangle|u\rangle. $$ If $x$ is in integer, then the outcome is guaranteed to be $y=x$...

The phase is applied to the overall wave function $|\phi\rangle$, therefore you can factor the phase to any individual qubit. For example if we have a wave function as a result of a controlled operation, with the first qubit as the control: $A|11\dots \rangle$, this can be factored as the tensor product $A|1\rangle \otimes |1\rangle \otimes |\dots\rangle$. ...

The key idea in understanding phase kickback is that phase factors do not belong to one register or the other, but instead belong to terms in superposition and are shared by the registers. For example, consider the phase kickback due to CNOT applied to $|{+-}\rangle$ $$ CNOT |+\rangle|-\rangle = \frac{1}{\sqrt{2}}\left(CNOT|0\rangle|-\rangle + CNOT |1\rangle|...

Part of the problem people usually have here is a sort-of-classical intuition. Because you're trying to describe the action of a gate such as controlled-$U$, we divide it up as "if the control qubit is something, do something on the target qubit". It makes it sound like the control qubit doesn't change, and it's only the target that changes. This ...

Remember that the states $|+\rangle$ and $|-\rangle$ form a basis. That means that any state $|\psi\rangle$ that you use can be written as $$ |\psi\rangle=\alpha|+\rangle+\beta|-\rangle. $$ By linearity, we can basically treat what these two components do separately. The $|+\rangle$ component is basically useless and gives the correct output with probability ...

It would still work if you rotated the $|−\rangle$ state, you refer to, by an angle with cosine less than $\frac{1}{L}$ where $L$ is the square root of the size of the search space (which is a power of 2). So it works with a different state which is a small rotation of the $|-\rangle$ state.

You are given a quantum circuit for $U$ compiled into the H/CNOT/T gateset. Derive a controlled version of $U$ by adding a control qubit $q$, replacing every H with a controlled H, every CNOT with a CCNOT, and every T with a controlled T. In all cases the new control goes on the $q$. Recompile the modified gates down into the H/CNOT/T gate set. Prepend and ...

An example of constructing (with help of Qiskit) a controlled version of some simple 4x4 unitary matrix: $$ U = \begin{pmatrix} \mathrm{e}^{i g_1} & 0 & 0 & 0 \\ 0 & \mathrm{e}^{i g_2} & 0 & 0 \\ 0 & 0 & \mathrm{e}^{i g_3} & 0 \\ 0 & 0 & 0 & \mathrm{e}^{i g_4} \\ \end{pmatrix} $$ where $g_s$ are some given ...

If you want to learn more generally about phase estimation, the book I am helping write has a whole chapter on it, Learn Quantum Computing with Python and Q# (chapter 8). Ping me here or via email and I can get you a discount code!

I understand, that cU has multiple eigenvalues with a factor s. How can be guaranteed that each of the controlled-Us will kickback the same eigenvalue? Or, why it is not important? All the $U$s in the various controlled-$U$ are the same $U$, with the same eigenvectors and the same eigenvalues. This is part of the construction of the circuit, and provides ...

As to "who discovered/invented the quantum phase estimation algorithm," in his 2011 lecture at Keio University describing the linear equations algorithm, at about the 18 minute mark Lloyd claims that it was inherent in the works of Von Neumann. That reminds me of the argument that "Gauss discovered the Fast Fourier Transform 160 years before Cooley and ...

The IBM Qiskit text has a section on this that you may find useful. For something more "academic" Mermin Sections 4.2-4.5, Schuld and Petruccione Sections 3.5.1-3.5.3, or Nielson and Chuang Sections 6.1-6.2 may have what you're looking for. Schuld and Petruccione also have references at the end of each chapter, which could be worth looking into.

Here is a basic example of a two system that might help you to see this better. Suppose I have these two circuits: Circuit 1: Which put the "Controlled qubit" in the state $|1\rangle$ and the "Target qubit" state in $H \big(X|0\rangle \big) = \dfrac{|0\rangle - |1\rangle}{\sqrt{2}} $. Note that this state, $|psi \rangle = \dfrac{|0\...

Have you seen this document? https://qiskit.org/textbook/ch-algorithms/shor.html Note that in Shor's algorithm, we use the quantum computer as a subroutine to essentially find the period of the function $$ f(x) = a^x mod N$$ where $a$ is a guessed value between $1$ and $N-1$. So you have to create different circuit to implement each of the guessed $a$. As ...

For the mathematical explanation, check here: Why is the action of controlled-Z unaltered by exchanging target control qubits? Maybe it would help you to see CZ in a different (symmetric) notation, like its current representation in Qiskit: from qiskit import * circuit = QuantumCircuit(2) circuit.cz(0,1) circuit.draw('mpl')

Without a bit more context of how they use the notation in the rest of the book, I'm not certain, but the way I would interpret that is saying "if the control qubit is 0, apply unitary $\hat U_{f(0)}$ on the target. if the control qubit is 1, apply $\hat U_{f(1)}$ on the target". If this is to be the case, let's see what the action is supposed to be. As you ...

The expression you obtain after applying the QFT contains sums of the unit square, $e^{2\pi i/2^n}$, which sum up to 0 if you sum over the full range of $2^n$: $$ \sum_{k=0}^{2^n - 1} e^{\frac{2\pi i}{2^n} k} = 0 $$ See here for explanations why this is the case. Now the inner sum in the amplitudes will also sum up to 0, if $(x - 2^n\theta)$ is an integer,...

3 things I see from your implementation of inverse QFT: SWAP gates are missing prior to applying Hadamard gates and cu1 gates. The Hadamard gate should come first before cu1 gates. The angles of cu1 gates, how I understand inverse QFT, should be different. Here is inverse QFT that worked for me with not touching other parts of the code: def qft_dagger(...

So, are you asking whether it's possible (in the qubit case) to perform an arbitrary map of the form $$ ae^{i\theta}|0\rangle+be^{i\phi}|1\rangle\rightarrow \frac{1}{\sqrt{2}}(e^{i\theta}|0\rangle+e^{i\phi}|1\rangle), $$ if $a$ and $b$ are unknown real numbers satisfying $a^2+b^2=1$? If this is the case, this is impossible. Consider a simple case where ...

If we express the action of $O_x$ on the basis $\mid i, \pm \rangle$ instead of $\mid i , b \rangle$ \begin{eqnarray*} O_x \mid i , + \rangle = \mid i , + \rangle\\ O_x \mid i , - \rangle = (-1)^{x_i} \mid i , - \rangle\\ \end{eqnarray*} Because we say auxiliary qubits must be started and ended with $0$, \begin{eqnarray*} O_x'' &=& (1 \otimes S_x ...