2
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ Does $f$ produce 1-bit output? $\endgroup$ May 8, 2022 at 8:28
  • $\begingroup$ No. It produces output of constant length $\endgroup$ May 8, 2022 at 8:44
  • $\begingroup$ Although I'm still interested if there is a solution for 1 bit output. $\endgroup$ May 8, 2022 at 8:44
  • $\begingroup$ For 1 bit output use quantum counting, and then take the solution mod 2 $\endgroup$ May 8, 2022 at 12:33

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

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

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