[Cryptography] Quantum computers and the Government

[Jerry Leichter]

>    John> Pretty confident.  Some calculations are amenable to quantum
>    John> methods, some aren't.  Only what one might call "reversible"
>    John> computations are, but those happen to include
>    John> multiplcation/factoring and exponentiation/logarithm.
>    John> Hashing, on the other hand, is not reversible because multiple
>    John> inputs hash to the same output and you can't tell which input
>    John> you started with.  So it's relatively straightforward to tell
>    John> whether a quantum computer could run an algorithm.
That's an over-simpliifcation.

> Can you give me some reading on this or places to start to understand
> why we think it is that  some computations are not amenable to quantum
> methods?
> I'd really like to understand why it is we believe that if there is a
> separation between P and NP, there is a separation between QP and NP.
> I mean I guess what I'm probably asking is to get a better understanding
> of the quantum computation model and how that relates to classical
> models I studied back at MIT.
There's a *huge* amount of work in this area.  An overview from the end of 1996 - https://people.eecs.berkeley.edu/~vazirani/pubs/bbbv.ps <https://people.eecs.berkeley.edu/~vazirani/pubs/bbbv.ps> - will give you a start.  Here's a quote that addresses exactly your point:

"It is natural to ask whether NP is a subset of BQP, i.e., can quantum computers solve NP-complete problems in polynomial time?  In this paper, we ... prove that relative to an oracle chosen uniformly at random, with probability 1, the class NP cannot be solved on a quantum Turing machine in time o(2^{n/2}).  We also show that relative to a permutation oracle chosen uniformly at random, with probability 1, the class NP intersect co-NP cannot be solved on a quantum Turing machine in time in time O(2^{n/2}).... We should emphasize they [these results] do not rule out the possibility that NP is a subset of BQP.  What these results do establish is that there is no black-box approach to solving NP-complete problems by using some uniquely quantum-mechanical features of QTMs.  That this was a real possibility is clear from Grover's result, which gives a black-box approach to solve NP-complete problems in square-root as much time as is required classically."

(The power of Grover's result is somewhat weakened by later work that shows that some ancillary computations have to be efficiently implementable for it to work.  This is the case for factoring, but the last I saw - I don't keep up with the field - it was unknown if it was true for inverting AES.)

Crystal clear, right?  :-)  It's a complex, very technical field.

                                                        -- Jerry

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://www.metzdowd.com/pipermail/cryptography/attachments/20210903/6d0a2afa/attachment.htm>