I am referring to the Quantum Search of Spatial Regions paper.

I must confess that the paper itself is a bit heavy for my level of mathematical fluency. Trying to understand it nevertheless and having some background in QC, I have stumbled upon the following presentation from Scott Aaronson himself.

Slide 19 outlines the subdivision algorithm for $d\ge3$ making use of recurrent subdivision and random picking of subcubes, wrapped in an amplitude amplification scheme.

My question would be - what is meant by picking a random subcube? A classical RNG? A measurement? And if so, how could that possibly fit into the amplitude amplification scheme, as the latter relies on keeping the entangled state?

Would somebody be so kind to shed light on this? Thank you in advance.

Kind regards, -- Stanislaw

  • $\begingroup$ I haven’t studied the paper in any detail but I envision picking random subcubes with a PRNG/random oracle. There are a lot of lovely “Grover+Birthday” results along these lines I think. $\endgroup$
    – Mark S
    Oct 13 '21 at 13:12
  • $\begingroup$ @MarkS any example of the "Grover+Birthday" approach? I would be very grateful for a sample paper of any kind. $\endgroup$
    – Stanislaw
    Oct 15 '21 at 7:56
  • $\begingroup$ Well, "Grover+Birthday" is a term I just coined in that comment, to refer to bounds for some quantum algorithms that are based on both Grover's algorithm and the birthday paradox working together. An example may be the collision problem described here. The "birthday" random picking is done with, for example, a hash/PRNG. $\endgroup$
    – Mark S
    Oct 15 '21 at 13:09

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.