$\newcommand{\Ket}[1]{\left|#1\right>}$ If we have the superposition $$\displaystyle \sum \dfrac{1}{2^n} \Ket x \Ket{ f(x)} \Ket 0 \Ket y \Ket{g(y)} \Ket 0 \Ket {\delta_{x,y}} ,$$ here $\delta_{x,y} = 1 $ if $f(x) = g(y)$, else $\delta_{x,y}=0$. I want to copy $\delta_{x,y}$ to qubit $\Ket 0$ by some ways so that it becomes superpositon $$\left(\displaystyle \sum \dfrac{1}{2^{n/2}} \Ket x \Ket{f(x)}\Ket {\delta_x} \right) \left(\displaystyle \sum \dfrac{1}{2^{n/2}} \Ket y \Ket{g(y)} \Ket{\delta_y} \right) \Ket 0 ,$$ means that $\delta_x = 1$ if $f(x)$ collides with some $g(y)$, and so does $y$. After that, apply Grover's algorithm on the first half and second half to find $x$ and $y$ that collides, in $O(2^{n/4})$ time complexity.

Is there any way to copy like this?

  • $\begingroup$ I may be misunderstanding something, but why wouldn't $\delta_x$ and $\delta_y$ always be equal to $1$? It looks like both $x$ and $y$ are $n$-bit strings which are iterated over all possible values. $\endgroup$ – dlyongemallo Jan 18 at 0:27
  • $\begingroup$ Yes, $x,y$ are $n$-bit string and are iterated over all values. If x collides with some y, then $\delta_{x,y} =1}$, and I copy it to $\delta_x$ and $\delta_y$. But to make the second superposition, if x collides with some y, we have to copy $\delta_x=1$ to all other $y’$ which do not collide x. How to do it? $\endgroup$ – Phuong Pham Thi Minh Jan 19 at 2:51
  • $\begingroup$ But if both $x$ and $y$ are iterated over all values, every single one of them will have a collision. If $x$ collides with some $y$, you say that you want to copy $\delta_{x} = 1$ to all other $y'$ which do not collide with $x$, but $y'$ must collide with some $x'$, no? In other words, there should be no need to do what you're asking. Instead of $x$ and $y$, did you mean for example some function $f(x)$ and $f(y)$? Otherwise, can you work out an example with $n=1$ maybe so I can see where there would even be a $|0\rangle$ to "copy" to? I think $\delta_{x}=\delta_{y}=1$ for all $x,y$ already. $\endgroup$ – dlyongemallo Jan 19 at 16:38
  • $\begingroup$ Sorry for my mistake. You're right, I mean $f(x)$ and $f(y)$ here. I am trying to quadratic speedup the classical meet-in-the-middle attack, so $x$ and $y$ are subkeys guesses of the first half and second half of a cipher. $\endgroup$ – Phuong Pham Thi Minh Jan 20 at 7:26
  • $\begingroup$ So you simply want to amplify the amplitude of all the components with $\delta_{x,y}=1$? So long as you have a unitary that produces that top state, this is exactly what the amplitude amplification algorithm does. $\endgroup$ – DaftWullie Jan 20 at 8:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.