Given a black box function f taking an input of length n bits, is there a quantum algorithm which can find the xor of all possible outputs of f, in less than 2^n calls to f?
$\begingroup$
$\endgroup$
4
-
$\begingroup$ Does $f$ produce 1-bit output? $\endgroup$– Egretta.ThulaMay 8, 2022 at 8:28
-
$\begingroup$ No. It produces output of constant length $\endgroup$– Yair HalberstadtMay 8, 2022 at 8:44
-
$\begingroup$ Although I'm still interested if there is a solution for 1 bit output. $\endgroup$– Yair HalberstadtMay 8, 2022 at 8:44
-
$\begingroup$ For 1 bit output use quantum counting, and then take the solution mod 2 $\endgroup$– Yair HalberstadtMay 8, 2022 at 12:33
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Assuming the output is of subexponential length, this can be done using quantum counting.
First use an adaptation of Grover's algorithm to find the input with the maximum length output as described here. You then know the total number of output bits you need to find.
Then for each output bit, use quantum counting to count the number of inputs which have 1 as the entry for that bit, and hence find the xor for that bit.