[Cryptography] Post Quantum Crypto

[Philipp Gühring]

Hi,

> > the scalability was demonstrated by D-Wave in the recent years.
> 
> That is far from clear.

>From my point of view, D-Wave demonstrated that you can scale up one
specific kind of quantum computers. 
I have been researching on the history of quantum computers, from the
first ideas about them by Richard Feynman
https://www.cs.berkeley.edu/~christos/classics/Feynman.pdf to the
development of Shor´s algorithm in 1994. And in the period between Shor´s
algorithm and 2001, there were 2 big open questions: Is it possible at all
to build a quantum computer that can run Shor´s algorithm? And between
1994 and 2010 the second big question was, whether it would be possible to
scale it up. The qubits are living in a 3-dimensional world where you need
to entangle them, and there are things like noise and 3-dimensional
topology and stability and a few other effects that make it really hard to
scale it up, and it wasn´t clear whether scaling it up much wider is
possible at all.
I read through the papers of IBM 2001 and D-Wave, to understand the
architecture any potential scalability issues (in space and in time), to
be able to extrapolate from that. For example, I saw some scalability
problems in the communication link between the quantum computer and the
outside world in the IBM concept, and saw that D-Wave seems to have solved
that particular issue.

>  The D-Wave device is not a quantum computer,

I haven´t found a proof for that claim yet. Do you have one?
I agree that it´s not a universal-register based quantum computer, and
that it does not fulfill the wishes people have from a quantum computer
due to the expectations that were raised. So from a simplified public
opinion point of view, I might agree with this sentence, but from the
technical point of view, I think I disagree.

> it’s a classical analog computer doing simulated annealing. 

Yes.

>  And it’s not even doing it all that well.

Possibly, yes. There are currently very very few "algorithms" available
for Quantum computers.

> www.scottaaronson.com/blog/?p=1400
> http://www.scottaaronson.com/blog/?p=2448

Those are interesting discussions, and I think I read the first one back
then. But I am wondering why they can´t provide a few simple easily
verifyable facts that dismiss the technological basis of D-Wave.
The points that I agree with are that D-Wave´s marketing had overstreched
their abilities. But I based my risk analysis on the technical papers and
documents of D-Wave, not on their marketing.
And I think the question, whether the D-Wave machines are faster than
classical algorithms or not is not really relevant for crypto.
There are a huge number of architectural issues around the quantum part of
the quantum computer that have a huge impact on the performance.
 
> Whether the D-Wave technology can be some day extended to implement
> real QC is an open question, but I´ll give long odds against.

In 2014 D-Wave claimed in a comment that they could extend it if they
wanted. I am not 100% sure about that claim, and whether the comment was
really meant that way, but it fits the impression I got from all their
underlying technology and the way they are working.

Best regards,
Philipp