Quantum algorithm: Difference between revisions

Revision as of 00:49, 7 February 2020

Revision as of 22:35, 11 February 2020

Line 100:

We have an [[Oracle machine|oracle]] consisting of n random Boolean functions mapping n-bit strings to a Boolean value. We are required to find n n-bit strings z₁,..., z_n such that for the Hadamard-Fourier transform, at least 3/4 of the strings satisfy

:<math>\left| \tilde{f}\left( z_i \right) \right| \geqslant 1</math>

and at least 1/4 satisfies

:<math>\left| \tilde{f}\left( z_i \right) \right| \geqslant 2.</math>.

This can be done in [[BQP|Boundedbounded-error Quantumquantum Polynomialpolynomial time]] (BQP).<ref>

{{Cite arXiv

| last = Aaronson | first = S.