A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

# Tag Info

8

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

8

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

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

4

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

4

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

4

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

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

3

Deutsch's algorithm is not faster on a quantum computer, Deutsch's algorithm is only possibe on a quantum computer. A classical computer cannot perform Deutsch's algorithm, a classical computer can only simulate Deutsch's algorithm. Forget about speed, more fundamental is that we are performing a type of computation that can never be performed, in any ...

3

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 = (... 3 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 ... 3 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 ... 3 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 ... 2 The circuit you gave implements an oracle for a function f(x) = 0, which is constant. You can observe that there are no gates leading from the top two wires (inputs |x\rangle) to the bottom wire (output |y\rangle). Since the oracle is supposed to transform |x\rangle|y\rangle into |x\rangle|y \oplus f(x)\rangle, and |y\rangle always remains ... 2 I will try to give an answer from complexity theory's point of view. This question should be asked in cs.stackexchange by the way. The Deutsch-Jozsa problem has an efficient algorithm on quantum computation and on a classical probabilistic Turing machine, so it is in BQP and BPP. There is no result that says: if you show a problem A in BQP and not in P, then ... 2 Let f be your favorite \mathrm{SAT} problem. For example, one that I like is: Are there integers x_1, x_2, x_3, each -2^{50}\le x_1,x_2,x_3 \le 2^{50}, with x_1^3+x_2^3+x_3^3=42? Write f as a sequence of irreversible \mathsf{NAND} gates, etc., and convert them to a sequence of reversible \mathsf{CCNOT} gates, etc. to determine a unitary ... 2 As everyone knows, all functions of quantum computing are inverses of each other. Hence, the 2 H gates cancel out. Quantum gates all have inverses, but the inverse of a gate is not necessarily the same gate, though Hadamard gates, which are the ones being most considered here, are their own inverse. I'm not sure if by "2 H gates" you mean the two gates ... 2 TL;DR: There are 8 possible outcomes, each with equal probability of being read. The final state has q[1] read as 0 in 4 of the outcomes, and read as 1 in the other 4 outcomes. Since you are only measuring q[1], you only see the two results, one with q[1] as 0 and one with q[1] as 1. They are both around 50% because each outcome had an equal probability of ... 2 I am not sure what the second question is about, but in the first one you are probably inquiring about the concept of "phase kickback": Why does the "Phase Kickback" mechanism work in the Quantum phase estimation algorithm? 2 There are really two different questions here. How can you figure out that a given output can be written as tensor product of two vectors? This is equivalent to asking: how do you figure out whether an output is separable? For pure states, which is what you are considering, this is rather easy. In your specific case (two qubits), you might simply notice ... 2 If you have already got, mathematically, to the point of having the vector (1,-1,1,-1)/2, you don't have to worry about the action of the controlled-not any more. You've already done that! All you have to do is factor the answer. Personally, I usually find the answer quite difficult to see when expressed in this way. Once you've got the answer you can ... 2 On a classical computer, you can recycle memory, so there is no need for storing all intermediate results. The main source of the higher performance of quantum computers is the possibility to do an operation with all different values you can store in n q-bits register at once. However, this is not a case always. For example, the evaluation of Boolean ... 1 @cgranade and I have a chapter on the Deutsch-Jozsa algorithm (Chapter 7) as well as implementations of the oracles for Q# in our book Learn Quantum Computing with Python and Q#. You can find the code samples for the book in the repo here. In particular, the oracles look like this: namespace DeutschJozsa { open Microsoft.Quantum.Intrinsic; ... 1 An oracle U_f is actually \mathrm{X} gate (or a negation). The circuit implementing the oracle is following Qubit q_0 is input and qubit q_{1} is output. Firstly \mathrm{X} is applied on q_{0}. This negate the qubit, however, we want to have an output on q_1. Therefore, we apply \mathrm{CNOT} which in this setting "copy" the q_{0} to ... 1 The (-1)^{x\cdot y} terms come from the matrix elements of H^{\otimes n}. To see this, start from considering the matrix elements of H. You can check that they can be written as H_{ij}=(-1)^{ij} where i,j\in\{0,1\}. The matrix elements of H^{\otimes n} are indexed by tuples of n binary numbers, that is, writing I\equiv (i_1,...,i_n), J\equiv(... 1 Indeed, the formula assumes that n=\infty, and is approximately correct if 2^n \gg k 1 I don't think you can factor. There are many cases where the result of the gate will produce a combined CNOT output (4 numbers) that cannot be factored. I think most states between two qbits is entangled from our perspective. So you cannot trust in factoring. Instead, the four products remain in memory while your program writes the data to both of your ... 1 The terms of expression do not cancel out in the balanced function case. We start with$$\frac{1}{2} (|0\rangle|0 \oplus f(0)\rangle - |0\rangle|1 \oplus f(0)\rangle + |1\rangle|0 \oplus f(1)\rangle - |1\rangle|1 \oplus f(1)\rangle) If $f(0) \neq f(1)$, consider the first two terms (the only ones which can cancel with each other, since the state of the ...

1

Finally, I found the answer myself there. The only interesting thing is the amplitude of $|0\rangle^{\oplus n}$. If the function is constant, it is $\pm 1$ and if the function is balanced, it is $0$. Hence, in the first case we are sure to measure all qubits in the $|0\rangle$ state and in the second case, we cannot measure all of them in this state (else ...

1

If you want to measure $|\phi\rangle$ in some basis $U|b_1\rangle,...,U|b_n\rangle$ instead of $|b_1\rangle,...,|b_n\rangle$, then you need to rotate the state "backward", i.e. measure $U^{-1}|\phi\rangle$ in $|b_1\rangle,...,|b_n\rangle$. The simple rule to find the direction of rotation is to consider the state and the required measurement basis together \$\...

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