back to article Quantum computing is so powerful it takes two years to understand what happened

In 2012 a group of Chinese quantum physicists pulled off an acclaimed success in quantum-based factoring, running an adiabatic quantum algorithm for the number 143, at the time believed to be the largest number ever factored in a quantum computation. It now seems that paper, here, could have overlooked something: in a new …

  1. Nigel Brown

    So what is it? *

    I'm afraid you lost me halfway through the opening sentence!

    *It's a big swirly orange thing in space!

    1. Ole Juul

      Re: So what is it? *

      Pics or it didn't happen.

      1. Forget It
        Go

        Re: So what is it? *

        Your pic sir:

        https://d262ilb51hltx0.cloudfront.net/max/834/1*YFBcLhwxjI2q2ko-Rxlw7A.png

        best read with this blog:

        https://medium.com/the-physics-arxiv-blog/the-mathematical-trick-that-helped-smash-the-record-for-the-largest-number-ever-factorised-by-a-77fde88499

        1. Chris Miller

          Thanks, Forget It

          So, if I understand it correctly (probably not), the method only works to factorise numbers that have two odd factors that differ by a power of 2 (e.g. 56153 = 233 x 241), and so could be easily defeated (for cryptographic purposes) by minor tweaks to the choice of the two large prime numbers used to compute the private key.

          1. YetAnotherLocksmith Silver badge

            Re: Thanks, Forget It

            Sort of - the reason for that is the fact they used a 4 bit device. If they'd used a (say) 6 bit device then it would have done the same for a different power series.

            The risk is that if they used a series of these machines and factorised lots of the series, then many keys would fall, because they would be part of these series. And currently, they are randomly found. If you start saying "That power series isn't allowed" you start reducing the keyspace quite a lot, and you increase the computational power required to make a key.

            Part of the "weakening" of the encryption by the TLAs was attacking the randomisation of the salts, meaning that there was a higher likelihood of the factors being in a given series. This means that instead of having to try and work through n log n worth of numbers, they could be sure it was in a subset of that. The smaller the subset, the faster and easier it is to break it by a sort of educated guessing, rather than having to try and brute force all the possible primes.

            (e.g. you introduce a subtle* "bug" so that one of the massive primes used ends in 3 or 7. That cuts your workload down massively, as 1, 5, 9 can be ignored, and no-one's ever going to notice unless they *really look*. That cuts your time to break the key from (say) 10 years to 4 years before you've even started. And in fact it is worse than that, because that's for one of the primes. If you did the same to the other, it drops from at best 5^5 = 3125 to 2^2 = 4. Which is quite a big drop! That 10 years becomes 28 days.)

            *You can be a lot more subtle than that. This is just to give an example.

          2. Michael Wojcik Silver badge

            Re: Thanks, Forget It

            factorise numbers that have two odd factors that differ by a power of 2 (e.g. 56153 = 233 x 241)

            233 and 241 differ by two powers of 2; that is, they have two bits that are different. 11101001 and 11110001, respectively.

            The write-up in that blog is abysmal - the author writes "factors differ by two", then "differ by only two", then "differ by two bits"; then it's back to "differ by two" again. Those are rather different conditions.

            The preprint on arxiv.org (PDF) is actually much clearer than the blog post:

            In fact, it turns out that the product of any two numbers differing at only 2 bits will lead to the [same three] equations

            That's it. If there are two factors that differ by exactly two bit positions (i.e., binary Hamming distance of 2), then these equations apply and you have the same Hamiltonian.

            As someone else pointed out, the magic number 2 is due to the number of qubits available. If you have 8 qubits, you can solve the Hamiltonian for products with factors that have binary-Hamming distance 3. If H(p,q) is the binary Hamming distance for two factors of the product, you need 2H(p,q) qubits to perform this operation and solve for p, q.

            (Note to Chris: The factors we're interested in are always odd, since we want prime factors, and we can eliminate 2 straight off.)

            1. Anonymous Coward
              Anonymous Coward

              Re: Thanks, Forget It

              Am I missing something here? I read that preprint as well as I could, and If the only requirement for the numbers is a hamming distance of 2, it is trivial to come up with MUCH bigger numbers than 56153, for example:

              7907 is 1111011100011

              7919 is 1111011101111

              7907*7919=62615533

              Does this mean Xu and co. also accidentally factored 62615533?

    2. WraithCadmus

      Re: So what is it? *

      So what is it?

      I've never seen one before Nigel, no-one has, but I'm guessing it's a White Hole.

      1. Ralph76

        Re: So what is it? *

        So that thing is spewing time back into the Universe?

      2. Tom Chiverton 1

        Re: So what is it? *

        So what is it?

        1. Over Informed Optimist

          Re: So what is it? *

          So what is it? ... Just kidding

          1. vonBureck

            Re: So what is it? *

            Somebody punch him out...

  2. Yugguy

    I have only one comment on this.

    Er, you what?????

  3. Tom 7

    Well this should revolutionise economics

    and ...

  4. Anonymous Coward
    Anonymous Coward

    Obsolete for whom?

    "the kind of quantum-based factorisation that would eventually obsolete current cryptography"

    From the little in the public domain, it seems fairly evident that Global Terror (tm) and their predecessors have used idiot codes since time immemorial. So the end of cryptography is more a problem for governments than either real world mortals being spied on by their own governments (because back-dooring undoubtedly defeats most of our efforts), and because no amount of computing power will crack an idiot code.

    Having had my privacy serially undermined by Western governments, I look forward to the day when they won't be able to keep anything like as much hidden

    1. Thomas Whipp

      Re: Obsolete for whom?

      Think authentication rather than privacy

      dont think this is such a big issue for website certificates either as under current CA arrangements its really very easy to get your own root CA if you have some cash to splash in which case you can issue new certs for any website you want to impersonate.

      Plus for serious players (APT types) they probably can compromise the client devices of people they are interested in and then HTTPS is utterly irrelevant.

      What this is more significant for is if you are using PKI based signing by a fixed key for any kind of validation - that is a big deal. Thats software components (think MS root keys), financial transactions, etc... there is a lot of "infrastructure" that this would completely wreck.

    2. Michael Wojcik Silver badge

      Re: Obsolete for whom?

      "the kind of quantum-based factorisation that would eventually obsolete current cryptography"

      There's a slight error in that quote. It should be "the kind of quantum-based factorisation that might eventually be a problem for the asymmetric cryptographic algorithms commonly in use today, forcing us to gradually switch to any of several so-called 'post-quantum' asymmetric algorithms at a probably negligible increase in processing cost, but has no consequences whatsoever for symmetric encryption".

      There, Richard - FTFY.

  5. Anonymous Coward
    Anonymous Coward

    Okay

    ....this sums it up nicely.

    http://3.bp.blogspot.com/_hZIY7V5QNVg/TLfWcPpTBMI/AAAAAAAAAEc/BapKUuEP7no/s1600/My+head+hurts.png

  6. Warm Braw

    Not Shor

    This particular factorisation didn't use Shor's algorithm, as far as I can understand. Does this mean that adiabatic quantum computation is actually an improvement in that it appears to (at least partly) factorise other numbers simultaneously?

    1. Michael Wojcik Silver badge

      Re: Not Shor

      Nothing special about adiabatic QC here, as far as I can see. If my understanding is correct (and it may not be), the technique should work with other QC implementations.

      Shor's is a general-purpose integer-factoring algorithm. This technique works only when you have a pair of factors that have a precise Hamming distance, and you have to do the algebra to enumerate and reduce the system of simultaneous equations, and then compute the Hamiltonian. Then you fire up the QC and let it find the values of the unknown bits. So it's not a magic box for factoring numbers.

      To be honest, I don't immediately see how you'd extend this to make factoring hard products (like the kind used in RSA) practical.

      I also don't know if it can be extended to attack discrete-log and EC, because I haven't studied in detail how Shor's is extended to do that, and I can't be bothered to right now.

  7. Andy The Hat Silver badge

    Obviously

    I thought they'd already considered that thing that they are talking about so I didn't bother to mention it ...

    I'm sure they tested "adiabatic algorithms" in face creams but didn't use them as it caused furrowing of the brow...

  8. TRT Silver badge

    Erm... whatever you say.

    It's about this point that I give up and set up a stall selling batik died tee-shirts.

    1. death&taxes

      @TRT

      Surely 'Batik Died'?

      Sad news though I didn't know him/her myself.

      1. TRT Silver badge

        dyed.

        My grandfather dyed during the war. Up at the local uniform factory.

        1. TRT Silver badge

          You could tell which of our fighting forces he'd been making cloth for that day by the colour of his skin when he got back. Blue-grey for the RAF, yellow for the desert forces, navy for the Navy, obviously.

          He got drunk after work one Friday and fell asleep in a garden hedge on his way home. He'd been dyeing for the army that day; DPM or camo as they used to call it. We didn't find him until Sunday morning.

      2. I am not spartacus

        Ah, but did she die in vain?

  9. Pascal Monett Silver badge
    Trollface

    Impressive

    Not only can quantum computing solve all solutions at once, but now we know that it can do so for more than one value at once.

    Only one problem left : extracting the solution that corresponds to the value you were expecting.

    Oh well, they'll have that sorted out in the next fifty years, no problem !

  10. Optimist

    You don't need a quantum computer to tell you that the factors of 143 are 11 and 13!

    1. Tom Wood

      Indeed, though that's not really the point though, is it.

      Though I'm lost as to the part about being able to verify the work with a classical computer. The whole reason factorisation problems are useful for cryptography is that the factorisation is hard, but the opposite, multiplication, is easy. So it should be trivial to verify the work by multiplying the factors together with a classical computer (or, in the case of 11 and 13, in your head).

      1. DragonLord

        They can simulate the factorisation problem with a classical computer running a virtual quantum computer. However the classical computer can only model so many qbits before it becomes infeasibly slow (kinda like trying to model an ipad using an 08086). This means that they can verify the results that a machine is providing by running it through their simulations to see if it comes up with the same answer.

        1. Michael Wojcik Silver badge

          kinda like trying to model an ipad using an 08086

          I assume that's supposed to be "8086".

          And no, it's not kinda like that. It's not like that at all. Different complexity classes.

  11. Anonymous Coward
    Anonymous Coward

    Its all Greek to me.

    “These have precisely the same form as the equations in the factorisation of 143, except with different variables. Therefore the Hamiltonian is also the same, except the qubits … represent different positions in the corresponding binary strings … Other numbers that we have discovered reduce to the same equations include 3,599, 11,663 and 56,153”.

    That's easy for you to say!

    1. lambda_beta
      Linux

      Re: Its all Greek to me.

      But what if the wave fuction never collapes? We have no answers, other than 42. Nobody will ever crack that code.

  12. David Pollard

    Bitcoin?

    I wonder if they have a bit of fun mining bitcoin during their coffee breaks.

    1. hplasm
      Thumb Up

      Re: Bitcoin?

      Mine one- mine them all at the same time.

  13. joeldillon

    I have to say...

    300 Kelvin is a very fancy way to say 'room temperature' :P

    1. DanDanDan

      Re: I have to say...

      Haha, thanks for that, I totally missed it on my first read. It's undoubtedly very important from a physics point of view, but for us plebs, room temperature would make more sense!

    2. Daniel Hall
      Flame

      Re: I have to say...

      26.8C - Thats some warm room!

      Its warm enough in here with the aircon set to 19 thanks

  14. D@v3

    quantum awareness

    as long as it wasn't a side effect of the quantum computer getting bored with such a measly problem, and deciding to solve something a little trickier in it's spare time

    1. Captain DaFt

      Re: quantum awareness

      Just let me know when it figures out the answer is '42'.

      Then I'll worry!

      1. Jes.e

        Re: quantum awareness

        "Just let me know when it figures out the answer is '42'."

        Two times three times seven Shirly?

        1. Anonymous Coward
          Anonymous Coward

          Re: quantum awareness

          a: "the ANSWER is '42'", not the question.

          b: 42 is seven times nine, around here anyway.

  15. ortunk

    so they asked a question and got back a theory

    I guess the 4-qubit quantum computer is a better intuitive mathematician then those guys... plus maybe it factored more primes but they did not realize it yet (as all this techno mumbo jumbo is far off the coffestain fortune telling scale still)

    On another note 42-qubit quantum computer may be needed to compute the answer which we know is 42, then we can work on the x-qubit computer to design the computer which will in turn hopefully provide us with THE QUESTION once and for all!

  16. Vociferous

    Quantum computing is a tricksy mistress

    The impression one gets is that wonks are poking the quantum computers and going "huh? what?".

    Case in point: it's still neither clear if the D-Wave computer is a quantum computer or just behaves like one, nor if it is faster (and if so how much) than a conventional computer.

  17. Anonymous Coward
    Anonymous Coward

    Despite that the only known final answer from the biggest ever made computer was 42

    1. bpfh
      Mushroom

      And this is why...

      The mice needed to make a bigger computer, and we all know how that ended for us....

POST COMMENT House rules

Not a member of The Register? Create a new account here.

  • Enter your comment

  • Add an icon

Anonymous cowards cannot choose their icon

Other stories you might like