3
$\begingroup$

I have two functions $f:\{0,1\}^n \rightarrow \{0,1\}^m$ and $g: \{0,1\}^m \times \{0,1\}^k\rightarrow \{0,1\}$ and I want to find a point $(x,y)$ such that $g(f(x),y)=1$ (let's assume there is only one). Can I do it quantum time $O(2^{\frac{n}{2}}(F+2^{\frac{k}{2}}G))$, where $F$ and $G$ are time complexities of $f$ and $g$ respectively? Any reference would be of great help.

$\endgroup$

1 Answer 1

5
$\begingroup$

In this work Estimating quantum speedups for lattice sieves: https://eprint.iacr.org/2019/1161.pdf, in section 3 they define the notion of a `filtered quantum search'. I think you should be able to use the $f$ in your problem as a filter and recover a complexity similar to what you mention. The idea would be to chain the search, with $f$ as the filter.

PS: Ideally this should be a comment, but I don't have enough rep for that.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.