10

Apply it twice: $$ O_xO_x|i\rangle|b\rangle=O_x|i\rangle|b\oplus x_i\rangle=|i\rangle|b\oplus x_i\oplus x_i\rangle=|i\rangle|b\rangle $$ Hence, $O_x$ is its own inverse, and therefore reversible. To prove unitarity, it makes more sense to prove that $O_x$ has eigenvectors $$ |i\rangle(|0\rangle+|1\rangle)\quad\text{and}\quad|i\rangle(|0\rangle-|1\rangle) $$ ...


10

I believe there are two issues here. The first isn't anything wrong with your statement, but rather that you could make a far stronger (non-quantum) statement by the same reasoning: $\mathsf{P}\neq \mathsf{BPP}$. Why is this? For testing if an $n$ bit function is constant or balanced with certainty (as required by $\mathsf{P}$), it could be that we have to ...


10

There are two questions here. The first asks how you might actually implement this in code, and the second asks what's the point if you know which oracle you're passing in. Implementation Probably the best way is to create a function IsBlackBoxConstant which takes the oracle as input, then runs the Deutsch Oracle program to determine whether it is constant....


9

Remember that when you define the oracle effect as $B_f |x \rangle |y \rangle = |x \rangle |y \oplus f(x) \rangle $, $f(x)$ is a classical function of a classical 1-bit argument, so you do not have a way to compute $f(\frac {1} {\sqrt 2} |0\rangle +\frac {1} {\sqrt 2} |1\rangle)$ (a function of a quantum state). The quantum oracles that implement classical ...


8

I think there are probably two points to make here: The way that one implements quantum computation is not by simply looking at the unitary matrix and building something out of that, in just the same way that classical computation is not performed simply by first building the truth table and working off that (otherwise all classical computations would be ...


7

If you see the operator only from the unitary matrix point of view and you enumerate all inputs/outputs, which makes you visualize the matrix, indeed you somehow already know the answer. However, imagine now $n$ is very large, say just $n>50$ or $n>60$, it becomes a bit difficult to store a $2^n * 2^n$ unitary matrix. But if you can compute the ...


7

In fact, in the original paper of Deutsch and Jozsa they actually implemented two oracles, here comes their procedure. If you omit the second $U_f$ and get a state $|\psi\prime>=\displaystyle\sum_{i=0}^{2N-1}(-1)^{f(i)}|i,f(i)>$, when quering the expectation value you need to put another $U_f$ on $|\phi>$ to get a state $|\phi\prime>=\...


7

Following up on @luciano's answer, I think you are envisioning a quantum computer as being fast at evaluating functions, when in actuality, quantum computers are better at evaluating global properties of functions (and not, necessarily, the function themselves.) For example referring to the Deutsch-Jozsa problem, consider two separate bags containing Boolean ...


7

This is because of what known as Phase kickback. The phase of the bottom qubit can kick back and create a relative phase change on the top qubit. This is a very useful and often use trick in quantum computing. In fact, it is fundamental to the Quantum Phase Estimation algorithm.


6

It is not possible at an information-theoretic level to do what you want to do. Let us suppose we have two pure states: $|\phi\rangle$ and $|\psi\rangle$, where $$ |\phi\rangle = \frac{1}{\sqrt{N}}\sum_{i=1}^N |x_i\rangle $$ and $|\psi\rangle$ is similar to $|\phi\rangle$ but with a few of the coefficients tweaked in some way. Notice that we're fixing just ...


6

To answer your first question, the quantum oracles are defined by their effect on the basis states $|0\rangle$ and $|1\rangle$, and if the oracle has to be computed on a superposition of basis states, its effects are expressed using the fact that the oracle is a linear transformation. This means that you never compute $f(|+\rangle)$; instead, to compute the ...


6

"Where is the parallelism in Deutsch-Jozsa algorithm?" Instead of inputting just 0 or just 1 into the black box, you input both 0 and 1 into the black box at the same time, because you send $\frac{1}{\sqrt{2}}\left(|0\rangle + |1\rangle \right)$ into the black box. As I understand, the reason why this problem can be solved in one iteration is ...


5

Overview To recap the one-bit Deutsch Oracle problem, there are four possible oracle functions: constant-0, constant-1, identity, and negation. The task is to determine whether the oracle function is constant (constant-0 & constant-1) or variable/balanced (identity & negation). You can do this using phases as follows: Rewrite the oracle function as ...


5

The controlled dot doesn't do anything: it merely observes the bottom qubit in order to decide whether to apply the 𝑋 gate onto the top qubit. In the answer below, the qubit that appears first is the control qubit, it maps to the bottom qubit in your diagram, and the second one is the target qubit. The CNOT gate works on two qubits at once. You can't ...


5

Notice that $\mathcal O_x$ is a permutation matrix. The matrix elements are $$\langle j, c\rvert\mathcal O_x\lvert i,b\rangle =\delta_{ij}\langle c\rvert b\oplus x_i\rangle =\delta_{ij}\delta_{c,b\oplus x_i}.$$ In other words, $\mathcal O_x$ is diagonal with respect to the first register, and, for each block corresponding to a given $i$, connects all and ...


5

There is no way to build the oracle in a way which would not defeat the point of Deutsch's algorithm - that's why it is an oracle-based algorithm. The only way would be if you would come up with an incredibly hard to compute function (this is, an incredibly long circuit) which would take one input bit $x$ and give one output bit $f(x)$ (but on the way could ...


5

(Based on the time limitation I assume we're talking about an undergraduate level project, and not something more advanced.) If you look at the questions about Grover's algorithm, you'll notice that a lot of them ask about implementing oracles for interesting tasks - or at least tasks more satisfying than looking for the state $|111\rangle$ :-) One ...


5

If you look at the formula you want to prove term-by-term, you'll notice that the sum and the $(-1)^f(x)$ part is the same in both formulas; you just need to show that $$H^{\otimes n} |x\rangle = \frac{1}{\sqrt{2^n}} \left( \sum_{y=0}^{2^n-1} (-1)^{x \cdot y} |y\rangle \right )$$ You can either show this strictly by induction (similar to this question but ...


5

Yes, it will depend on $n$ because sampling with replacement is assumed in the proof, which doesn't make sense if $n$ is finite. Intuitively, if a function $f$ really is balanced, and first output corresponding to certain random input is $0$ or $1$, then the probability that the second output corresponding to some other random input will be the same is less ...


5

Here the subscripts are of the form $1i$, where $i$ is the label of the subsystem (recall that you are using two qubits for this $\left|\psi\right>_0=\left|00\right>_{1}$). So any product of subscripts can be written as $\left|q_0\right>_{10}\left|q_1\right>_{11}=\left|q_0q_1\right>_{1}$ with $q_0,q_1\in\{0,1\}$ in this convention, which makes ...


5

There aren't many examples! The main reason for advantages in quantum computers is the ability to constructively combine amplitudes - if you've only got 1 qubit, there aren't any amplitudes to combine! The best use case I can think of is randomness. A quantum computer (implemented with arbitrary error) could theoretically be a near perfect source of entropy,...


5

This is just a compact way of representing the Hadamard operator. The summation operator can be expanded, yielding: $$ \frac{1}{\sqrt{2}} \Big( (-1)^{x \cdot 0} | 0 \rangle + (-1)^{x \cdot 1} | 1 \rangle \Big) = \frac{1}{\sqrt{2}} \Big( |0\rangle + (-1)^x |1 \rangle \Big) $$ This occurs because the matrix representation of the Hadamard operator is: $$ \frac{...


5

This is just a convention. People tend to write $|01 \rangle$ instead of $|0 \rangle \otimes |1\rangle $, but they mean the same thing. In this case, $$ \overbrace{|0\rangle \otimes |0\rangle \otimes \cdots \otimes |0\rangle}^{n \ \ times} \otimes|1\rangle = |0\rangle^{\otimes n} \otimes |1\rangle = |0\rangle^{\otimes n} |1\rangle$$ So it is just a matter of ...


5

TL;DR: No entanglement is created in the course of Deutsch's algorithm. Generalization Deutsch's algorithm is a special case of Deutsch-Jozsa algorithm with $n=1$ qubits in the query register. Generally speaking, in the study of algorithms one should account for the dependence of algorithm's properties on input size. Therefore, we will look at a slightly ...


4

There are many different variants depending on what it is precisely that you want to achieve (note, this was written before recent edits, although I think there is still value/relevance in this more general answer). The closest analogy to the Deutsch-Jozsa algorithm is probably to say that you're given one of two states, and you want to know which you've ...


4

This is not so straightforward, I suspect. The issue is being able to distinguish between the constant case (e.g. every input gives output 0) and the case where only one input returns 1, and all others return 0. To distinguish these cases is essentially a Grover Search (the return of 1 being essentially a marked item that you want to search for the existence ...


4

To measure, observe that you are simply projecting a quantum state onto some basis set of vectors. First, I will note that this state is not normalized. Let us first define the following quantum state. $$|\psi_i\rangle = \begin{pmatrix}1\\-1\\0\\0\end{pmatrix}.$$ Then, calculating the corresponding probability yields: $$|\langle \psi_i|\psi_i\rangle|^2 = (...


4

It is limited to matrix $U_f$ which maps $|x,y\rangle$ to $|x,y\oplus f(x)\rangle$, and the little thought is $$U_f|x,-\rangle=\frac{1}{\sqrt{2}}(|x,0\oplus f(x)\rangle-|x,1\oplus f(x)\rangle)=$$ $$=\begin{cases} |x,-\rangle & \text{if }f(x)=0\\ -|x,-\rangle & \text{if }f(x)=1 \end{cases}=(-1)^{f(x)}|x,-\rangle$$ where $x\in\{0,1\}$ or generally $x\...


4

Your first formula is not correct. The correct formula for Hadamard gates for the arbitrary $|x\rangle$ from the calculational basis is (it can be proved by induction): $$H^{\otimes n}|x\rangle=\frac{1}{\sqrt{2^n}} \sum_{y=0}^{2n-1}{(-1)^{x\cdot y}}|y\rangle$$ where $x\cdot y=x_0y_0\oplus x_1y_1\oplus x_2y_2\oplus ...\oplus x_ny_n$ In case $|x\rangle = |0\...


4

Let's say that the first bit of $s$ $s_0=1$ (the argument will be exactly the same for any bit, just for convenience). You can split the space of inputs $x \in \{0,1\}^n$ in two halves: one half where $x_0 = 0$ and the other half where $x_0 = 1$. For each bitstring $x$ from the first half you'll have a bitstring $\tilde{x}$ from the second half which will ...


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