6 ms·

Thinnest silicon-chip wires refuse to go quantum

42 points by nickolai 15y ago

radarsat1 15y ago
Is it bad news when quantum computing has bad news? I'm torn on the subject. There are lots of interesting problems that might be solved or at least drastically sped up by quantum computing, such as optimization problems in engineering. However, security, which we generally deem essential in everyday transactions, depends purely on a lower limit to the time it takes to factor a large prime using known technologies. Similar for other essentials, such as privacy and anonymity. Quantum computing would be good in some ways, but terribly bad in others.
- comicjk 15y ago
  Any process that's much harder in one direction than the other is effective for this purpose. It helps that multiplication is very easy and factorization is very hard, but that's not the only way to hide a key in plain sight.
- dfranke 15y ago
  DJB has done quite a bit of research on what crypto could look like if large quantum computers ever become a reality. http://pqcrypto.org/ http://pqcrypto.org/
- Retric 15y ago
  If a Quantum computer can factor a 4096 bit number, but not a 8192 bit number then you can just use larger key's. So the real question is how much harder does it become to factor ever larger numbers and from what I read that's still an exponential problem for Quantum computers.
  - dfranke 15y ago
    from what I read that's still an exponential problem for Quantum computers Shor's algorithm is cubic, not exponential, in the log (i.e. the number of bits) of the number being factored.
    - Retric 15y ago
      The difficulty is not in time, but in accuracy of measurement. In other words the signal strength directly depends on the size of number factored.
- jerfelix 15y ago
  >> the time it takes to factor a large prime using known technologies. This is a common misconception (or perhaps common typo). Factoring large primes is trivial. It's those pesky composite numbers that are the product of two large primes that contribute to the strength of cryptography.
  - chc 15y ago
    In fact, easy factorization is the definition of a prime number. Given a prime number X, we know immediately that it has only two factors: 1 and X.
  - radarsat1 15y ago
    Right :)
jxcole 15y ago
> It could be bad news, though, for the super-fast quantum computers that are hoped to come next. It doesn't sound like it. It sounds like this is a very special property of phosphorous infused nanometer wide wires. It sounds like if you want quantum effects you could just, you know, not infuse the phosphorous. It's not like quantum theory has been disproven.

42 points by nickolai 15y ago

Is it bad news when quantum computing has bad news? I'm torn on the subject. There are lots of interesting problems that might be solved or at least drastically sped up by quantum computing, such as optimization problems in engineering. However, security, which we generally deem essential in everyday transactions, depends purely on a lower limit to the time it takes to factor a large prime using known technologies. Similar for other essentials, such as privacy and anonymity. Quantum computing would be good in some ways, but terribly bad in others.

comicjk 15y ago
Any process that's much harder in one direction than the other is effective for this purpose. It helps that multiplication is very easy and factorization is very hard, but that's not the only way to hide a key in plain sight.
dfranke 15y ago
DJB has done quite a bit of research on what crypto could look like if large quantum computers ever become a reality. http://pqcrypto.org/ http://pqcrypto.org/
Retric 15y ago
If a Quantum computer can factor a 4096 bit number, but not a 8192 bit number then you can just use larger key's. So the real question is how much harder does it become to factor ever larger numbers and from what I read that's still an exponential problem for Quantum computers.
- dfranke 15y ago
  from what I read that's still an exponential problem for Quantum computers Shor's algorithm is cubic, not exponential, in the log (i.e. the number of bits) of the number being factored.
  - Retric 15y ago
    The difficulty is not in time, but in accuracy of measurement. In other words the signal strength directly depends on the size of number factored.
jerfelix 15y ago
>> the time it takes to factor a large prime using known technologies. This is a common misconception (or perhaps common typo). Factoring large primes is trivial. It's those pesky composite numbers that are the product of two large primes that contribute to the strength of cryptography.
- chc 15y ago
  In fact, easy factorization is the definition of a prime number. Given a prime number X, we know immediately that it has only two factors: 1 and X.
- radarsat1 15y ago
  Right :)

jxcole 15y ago

> It could be bad news, though, for the super-fast quantum computers that are hoped to come next. It doesn't sound like it. It sounds like this is a very special property of phosphorous infused nanometer wide wires. It sounds like if you want quantum effects you could just, you know, not infuse the phosphorous. It's not like quantum theory has been disproven.