Submitted by giuliomagnifico t3_zuxy0d in technology
Comments
nagareteku t1_j1m6fas wrote
Simulations and cryptography mainly. It might have potential to reduce time complexity of algorithms from exponential to quasi exponential or even polynomial time (n-bit encryption).
Computations that may take longer than the age of the universe to perform on classical computers can now be approximately computed on quantum computers on a practical time scale of mere months or years.
Quantum computers are however very similar to Field Programmable Gate Arrays. They are specifically designed for one fixed algorithm at a time, but perform extremely well at it.
This means that it will likely be unable to run Far Cry or Crysis, just like how bitcoin miners cant crack your passwords, nor Deep Crack can stream and record 4K video.
shadowalker125 t1_j1m7r5w wrote
>Quantum computers are however very similar to Field Programmable Gate
Arrays. They are specifically designed for one fixed algorithm at a
time, but perform extremely well at it.
Wouldn't that make it more like an ASIC rather than an FPGA? Or can they be changed?
nagareteku t1_j1mfh79 wrote
Variables such as temperature of qubits, voltage and time of laser pulses can be changed. The arrangements of specific quantum gates can be varied as well. Unlike an ASIC, quantum computers can be reconfigured from time to time to fit the required algorithm.
For now, quantum computers are far from general-purpose, and even then it will be redelegated into a discrete "QPU" card similar to your GPU for quantum-related computing purposes.
Affordable room temperature and pressure superconductors will need to be mainstream before that happens.
squidmanwillie t1_j1opptr wrote
Did they ever solve the EC issues with quantum?
[deleted] t1_j1mw80o wrote
[deleted]
troyboltonislife t1_j1n1pa7 wrote
will this be used for machine learning at all? can these computers do the linear algebra used in machine learning?
nagareteku t1_j1nf075 wrote
Nobody knows what would happen in the future, but I would guess that in very niche use cases such as the Travelling Salesman problem (TSP). For classical computers the most commonly used is the Held-Karp algorithm that solves the TSP in just O(n^(2)2^(n)) compared to the naive (n!). The best quantum exact algorithm is Ambaninis algorithm at O(1.728^(n)) found in 2019.
Quantum chips can be used to accelerate machine learning for pathfinding AI that may face the TSP, such as for location app servers and self driving cars.
noideaman t1_j1ngjvs wrote
Notice, you didn’t reduce complexity to polynomial switching to quantum. We still don’t know if NP-Complete problems can be solved in polynomial time on a quantum computer. If I recall, the top theoreticians think no.
nicuramar t1_j1nv1yn wrote
Yeah, BQP (the problem class solved by quantum computers) is generally believed to be disjunct from NPC.
_Asparagus_ t1_j1nkwct wrote
Ambanini's algorithm will almost certainly never be used practically. It relies on Grover search to achieve its speedup, which has been basically shown to not be practical in the foreseeable future (see here for example. Held-Karp isn't used in practice either, since the exponential complexity is detrimental very quickly, and instead heuristics are used (this usually for example what popular software like Gurobi does). So extremely unlikely that TSP will be something quantum will help us with
troyboltonislife t1_j1nlb5y wrote
is held karp an approximation or does it solve it fully?
_Asparagus_ t1_j1njvo6 wrote
No, it won't. ML applications of anything quantum are extremely limited, especially in this regime of qubit numbers.
troyboltonislife t1_j1nllvd wrote
I guess I am not fully understanding of what calculations these computers are good for? I guess I thought they would be able to do something like linear algebra (multiplying many numbers together quickly) but it sounds like no
nicuramar t1_j1nv8jm wrote
The are good for solving problems in a class called BQP. There is a list here: https://cstheory.stackexchange.com/questions/31139/problems-in-bqp-but-conjectured-to-be-outside-p
professorDissociate t1_j1n60ey wrote
I feel like AI will eventually be something that really takes off thanks to QPUs.
craigularperson t1_j1ncqps wrote
Okay, now explain it to me like I am five?
nagareteku t1_j1ngso4 wrote
Quantum chips will solve some math problems faster than normal computers. It is unlikely these chips will be used to run computer games.
BronzeHeart92 t1_j1ptn6m wrote
One can only imagine tho what sorts of games these would have in future...
Gekokapowco t1_j1ngg4m wrote
Is it like a really fast CPU? Exceedingly fast at doing a single, potentially complex task? Vs a GPU which can do a lot of simple tasks at once?
km89 t1_j1ohf92 wrote
Sort of, but not really.
It could be faster than classical computers at a specific task, yes.
But it's not just churning through the same steps a classical computer would, faster than a classical computer would. It's something entirely different, which is why the biggest benefit is likely going to be the simulation of systems we can't currently simulate.
So it's not like a really fast CPU, the way a car is a faster vehicle than a horse. It's more like a petting zoo versus a conservation zoo. Some of the same things are present in both, but they really have almost entirely different purposes.
Extension_Bat_4945 t1_j1nrzrc wrote
What I do wonder tho is, how will all these investment return itself? I can’t imagine a good business case for now…
danielravennest t1_j1qusz1 wrote
Quantum computers have the potential to solve certain kinds of problems faster than regular computers. IBM is a computer company, so they are investing in quantum computer research. Sometimes research doesn't pay off, but you never make progress unless you try.
Extension_Bat_4945 t1_j1rgsml wrote
I get that, but normally companies mostly invest in technology/research that will profit in the future. And I’m sceptical quantum computing can return the investment, as I don’t see a business model yet and the investment has been huge.
maqp2 t1_j1tlzza wrote
One extremely useful purpose is protein folding which is what IBM (that the article is about) is also doing: https://protein-folding-demo.mybluemix.net/
the tl;dr is it will result in much faster faster medicine/vaccine development.
nicuramar t1_j1nuwen wrote
> Simulations and cryptography mainly. It might have potential to reduce time complexity of algorithms from exponential to quasi exponential or even polynomial time (n-bit encryption).
Yeah, so cryptanalysis, not cryptography (encryption, decryption, signing, verifying) so much. Cryptanalysis is however still completely infeasible on today's quantum computers.
[deleted] t1_j1nvy20 wrote
[deleted]
workerMcWorkin t1_j1orozx wrote
Does this mean that quantum computers could handle redundant loads in massive proportions?
I’m thinking replacing servers and such.
pm_me_wet_kittehs t1_j1qfjt9 wrote
pretty much anything that current tech can do efficiently, is not a problem a quantum computer can, and vice versa.
Goliath--CZ t1_j1nuj32 wrote
So you're saying that there might one day be a quantum computer that can only run crisis extremely well?
CreamofTazz t1_j1m59n4 wrote
So far quantum computers are only really good at solving complex math equations faster than digital computers
Mind you a lot of encryptions are just really complex math equations that your computer is given the answer to. Because QCs use superpositions of qubits (meaning they're in a complex state of 2 or more variables) they're able to hold significantly more information per qubit than a bit (which is just a single state of 0 or 1).
nagareteku t1_j1mhvgd wrote
Qubits do not store any more information than bits, it is just that the representation of n qubits requires 2^(n) bits because there are 2^(n) different combinations that n qubits can take.
Qubits "store" just as much information as bits, the primary difference is that qubits have a probability of being observed at both states at once. Consider a 2-level state qubit with state |0> ground and |1> excited. A quantum state can be a normalised linear combination of |0> and |1>. It does not consist of every single state similar to how a pair of spinning D20s does not store all 400 possible combinations.
When observed, the qubit collapses to either |0> or |1> with their respective probabilities depending on the observable. Repeated measurements will only show the same result, as predicted by the Born Rule due to wavefunction collapse. This means that while each qubit holds a superposition of both |0> and |1>, when measured, it will produce a fixed result of length 1 bit.
Such a system produces only probabilistic results, and not definite results from the classical computers we are used to. Quantum computing will make a lot of brute-force algorithms scale better, but it wont replace classical computers, nor provide a universal speedup or extreme amounts of storage. Furthermore, the larger the number of qubits, the harder it is to ensure that all qubits are properly isolated from each other.
nicuramar t1_j1nvke3 wrote
> Qubits do not store any more information than bits
How don't they, though, when each qubit requires a complex number (with modulus 1) to describe? Even if this information isn't directly available to measurement.
Shorts_Man t1_j1oekjw wrote
Are quantum processors only good for one calculation since all the qubits are collapsed afterwards?
sirbruce t1_j1mx8i3 wrote
> it wont replace classical computers, nor provide a universal speedup or extreme amounts of storage.
That's a very bold and definitive statement about future technology. In truth no one can really know what quantum computing might enable in the future.
Also, for someone making definitive statements,
> due to wavefunction collapse
is an odd choice of phrase given that wavefunction collapse is ill-defined and not even proven to actually exist.
skittlesmcgee33 t1_j1n8rvb wrote
What I’m most excited for is simulations of quantum systems - particularly in biotech. Today we can only really model the simplest of molecules accurately. There’s just too many degrees of freedom we can’t accurately predict within a quantum system.
And in biology form = function. Know how it’s structured, and you can know how it’ll behave. Will be huge for new treatments.
n351320447 t1_j1mdqai wrote
Cracking bitcoin
nagareteku t1_j1mjlky wrote
Maybe the US government already has the capability to crack SHA256 hashing and AES encryption using quantum computing accelerators. This could be old declassified technology.
If ₿ had been cracked there are far more significant vulnerabilities that would be uncovered. A malicious actor would keep the technology secret while gaining remote access to banks and numerous computing devices.
I believe that while quantum computers have not yet been used to mine or steal bitcoins, it is an eventuality and a large pot of gold for malicious uses of quantum computing.
StinkiePhish t1_j1n9bhj wrote
It will crack elliptic curve cryptography before hashing or symmetric encryption (AES). For bitcoin, that means the secp256k1 curve.
It's estimated that 2,330 qubits with error correction are needed to crack secp256k1. This IBM computer does not have error correction so we're not near half way there.
KAMSPioneer t1_j1noanj wrote
Totally. Just to be clear for the thread, a useful quantum computer will break ECC way, way before AES or SHA2.
pm_me_wet_kittehs t1_j1qg1oa wrote
for symmetric algorithms, a quantum computer would turn 256 bits of security into the equivalent of "Only" 128 bits. Double the key length amd any advantage just goes up in smoke. quantum won't help in a practical manner for AES
maqp2 t1_j1tmb9l wrote
Also, SHA256 does lossy compression, and obtaining preimages larger than 256 bits can not be done at all, QC or not.
nicuramar t1_j1nvptv wrote
> Maybe the US government already has the capability to crack SHA256 hashing and AES encryption using quantum computing accelerators. This could be old declassified technology.
That's extremely unlikely to be the case. Especially since quantum computers don't provide any useful speedup for those applications.
lunartree t1_j1mdyez wrote
Breaking encryption.
RubberPny t1_j1m6m33 wrote
IIRC they are super useful for financial number crunching and forecasting.
N3UROTOXINsRevenge t1_j1nptvx wrote
How the hell says fry cry? It’s either doom or crysis.
eggybread70 t1_j1nrqem wrote
Oops. I fucked up. You're right, it should be Crysis.
eggybread70 t1_j1mhp30 wrote
Thanks, nerd bros.
Alucard256 t1_j1mjei6 wrote
The most simple answer I can come up with is this: "classical computers" (as they are now known) work with 0's and 1's only, which can be thought of as "yes" and "no" only. Which in turn makes them great at anything with definite in inputs and leads to everything computers can do today. The problem is, it makes them very bad at anything that needs to deal with "maybe" and "probably" at all.
Quantum computers in contrast, work exclusively with "maybe" and "probably". Which means things like "true AI" (like C-3PO) will be possible. Weather forecasting will get MUCH better. Machines won't be limited to doing "exactly what you said"... they will be able to "do what you meant". Anything having to do with "probability" instead of "certainty" (which is currently nearly impossible to work with) will suddenly be as easy as using Excel to record item prices and produce an average.
In addition to all of that, quantum computes work with much more information at a time. Again, keeping it very simple: classical computers work with individual bits to make a byte which represents (roughly) a single letter or number; quantum computers can work with entire concepts at a time.
All of this is also why "what kind of solutions will it excel at?" is a really hard question. It's like trying to come up with answers about what the internet will be good for... in 1910 or so.
Treczoks t1_j1mzvci wrote
Primarily just quantum benchmarks and academic uses. Those toys are still years from being even remotely useful for real-world, practical calculations.
dutch_meatbag t1_j1nmoyc wrote
That was a blast from 2004.
Sk8nk t1_j1mtqtw wrote
Creating holographic wormholes.
Physicists Create a Holographic Wormhole Using a Quantum Computer
itdood t1_j1mp2la wrote
It's estimated that 6600 q-bits are required to break 256b AES. Given the road map this could happen in the next 4-6 years.
mrlazyboy t1_j1nhdg4 wrote
“Breaking” a crypto system usually means that you can decrypt a message faster than simply brute forcing the key. An example is DES which had a key space of 2^64, but only required 2^56 brute force attempts.
If I’m remembering my crypto correctly, quantum computers can break AES256 with 2^128 guesses, which is still effectively infinite from a practical perspective
jared555 t1_j1of2w6 wrote
Technically then AES is "broken" using conventional means but only barely.
mrlazyboy t1_j1ohtkh wrote
Which mode of operation?
jared555 t1_j1ombmi wrote
mrlazyboy t1_j1ov2cl wrote
That’s a theoretical attack (not practical) and it looks like it’s only applicable to ECB mode, not something like CBC or GCM
jared555 t1_j1srlsr wrote
Isn't any attack that we don't have the computational power to test going to be theoretical?
mrlazyboy t1_j1su83d wrote
Not necessarily, but it depends.
Anything worth securing is using AES256 with GCM so this attack in particular has a computational complexity of 2^254 which is effectively infinity. The computational complexity of this problem is probably greater than the number of atoms in the universe.
Even using a quantum computer, the computational complexity using this attack would be equivalent to AES128 which is still a number you don't have the ability to even conceptualize.
If you want practical attacks against this type of thing, you should check out the BEAST, Lucky13, and CRIME attacks. Those are practical attacks against SSL and TLS.
Practical attacks are those you can actually execute in the wild. I think CRIME (a chosen plaintext attack that takes advantage of compression) only requires about 20,000 messages which is relatively small.
maqp2 t1_j1tmlug wrote
Yeah, the 1.6-bit improvement is roughly 3.03x improvement. It's interesting we haven't yet seen snake oil claims like "AES 66% broken". In layman's terms, it's kind of like having to eat a cake that's 1/3rd the size of our galaxy. Sure, you got rid of 2/3rds of the cake size but your stomach will only fit so much.
wthulhu t1_j1ojprp wrote
For reference; the earth is about 2^92 grams.
nicuramar t1_j1nvznu wrote
AES isn't really susceptible to quantum attacks except with Grover's algorithm, which isn't effective because it can't parallelise very well. So I don't know where that 6600 number comes from.
Also, note that that would be error corrected qubits, which these chips don't have.
sumguysr t1_j1n9e5c wrote
Source please? My understanding was quantum computing only halves the difficulty of breaking symmetric encryption like AES but completely breaks current asymmetric encryption like RSA
nagareteku t1_j1njxg2 wrote
Grover's algorithm more than "halves" the difficulty of AES, it square roots it.
For a brute-force attack, 128-bit AES will now take 2^(64) rather than 2^(128) operations, and 256-bit AES will now take 2^(128) rather than 2^(256) operations.
To visualise the difference, 2^(128) is 18,446,744,073,709,551,616 times larger than 2^(64) and 2^(256) is that amount squared times larger than 2^(128).
Given a rate of a billion guesses per second, a single 6600-qubit quantum chip can crack AES-128 in 585 years. If we run a million cores of quantum chips in parallel, then in about 5 hours AES-128 is broken even when using a naive brute force attack. A well funded state actor could cuild such a machine, and easily decrypt anything encrypted on less than 128-bit of cipher.
256-bit AES will take a little longer, since 2^(128) is still quite a large number (3.4*10^(28)). Fortunately (or unfortunately), there exists a quantum attack on 256-bit AES with only 2^(100) operations required, although it might take 2^(100) bits (1.268 quettabytes) of storage and still require 2^(36) times more computational power than cracking AES-128.
For now, AES-256 is safe, but AES-128 is vulnerable. AES-256 may be slower than AES-128 but do not skimp on cybersecurity!
KAMSPioneer t1_j1npnnm wrote
All completely true, but the last paragraph should probably be taken with a grain of salt. For non-PQ threat models, AES-128 is totally fine. In fact key schedule attacks against AES-256 that could bring attacks down to 2^70 time (!!) do not affect AES-128.
None of that is to say that AES-256 is broken -- it's still quite safe. But unless you have strong and imminent concerns about quantum attacks on your cryptosystem, AES-128 is almost definitely not vulnerable. Most experts agree that your time is better spent worrying about everything around the primitive than the choice of primitive itself.
I just don't want anyone alarmed by the idea that there is a nearly-practical attack on AES or something. That's a long, long way off.
nicuramar t1_j1nw5o7 wrote
> Grover's algorithm more than "halves" the difficulty of AES, it square roots it.
Yes, but unfortunately it also makes it impossible to run the algorithm in parallel, making it more or less useless in practice.
itdood t1_j1n9mik wrote
KAMSPioneer t1_j1nrm7d wrote
This source says 6600 error-corrected qubits and the source article OP posted appears (though it's not completely clear to me) to not be utilizing error correction. I suspect this dampens the usefulness of IBM's new machine in implementing Grover's.
nirad t1_j1og4dn wrote
I wouldn't be surprised if the DOD already has it.
winkler t1_j1ov5wj wrote
Noob question but if I had 7 1000q-bit QCs could I break this encryption?
maqp2 t1_j1to2vx wrote
tl;dr No.
ELI5: The goal in quantum computers is to get many qubits into into a superposition where they are sort of connected to each other. As the number of qubits inside a single quantum computer is increased linearly, the problem size they can solve grows exponentially. If you add a second quantum computer, you're only doubling the computational power. With seven computers you can parallelize breaking of e.g. 7 keys, but the number of qubits inside a single quantum computer determine the size of the encryption key you're able to break.
Finally, I hope I didn't ruin some horcrux reference here, with the seven and all.
arfbrookwood t1_j1moqr3 wrote
What’s interesting is how the chandelier puts out analog data that is processed into digital data by a companion classical computer and feed back into it.
Trax852 t1_j1n5iyz wrote
IBM, there's a company that should be Microsoft's equal yet rarely hear of it.
Current_Individual47 t1_j1o0ssa wrote
Different business models lead to different outcomes.
ColdRest7902 t1_j1mav7j wrote
Factoring prime numbers
maqp2 t1_j1to9oc wrote
Not to nitpick but the factors of a prime number are already known, e.g. the factors of 13 are 13 and 1. What you're usually factoring in these cases are semi-primes, that are the product of two prime numbers.
Moonhunter7 t1_j1oit25 wrote
Wasn’t Qubit that weird video game from the 90’s with the big nose???
tms10000 t1_j1pex77 wrote
Close but no. It was Qbert.
freelikegnu t1_j1oley5 wrote
They are waiting for bios update and then watching the forums for posts by early adopters before proceeding.
awhatname t1_j1mrbg2 wrote
Can it run Shor's algorithm? What's the largest number they've been able to factor?
maqp2 t1_j1tof1b wrote
As per https://en.wikipedia.org/wiki/Integer_factorization_records#Records_for_efforts_by_quantum_computers, the largest number that Shor's algorithm has been used to factor, is 21.
Ecyclist t1_j1opl84 wrote
Can it solve the mystery of why my brain doesn’t make dopamine? If not it’s useless to me.
whawkins4 t1_j1pd3v2 wrote
There are five people on Reddit who really know what a Qubit is, and I am one one of them.
Apertureaddict t1_j1pl1fn wrote
And it still can't run Adobe Premiere smoothly.
BronzeHeart92 t1_j1ps2b8 wrote
Do you think it would be possible to use the net with these things?
dangil t1_j1pvz2x wrote
it doesn't matter.. it doesn't work. there is and never will be quantum supremacy.
it's like thinking quantum entanglement will allow faster than light communication
5p0k3d t1_j1qoibg wrote
What is an example of a computation that would take a classic computer ages to complete that a quantum computer can complete in less time?
maqp2 t1_j1tp12b wrote
Example problem: Find out which two prime numbers were multiplied together to produce the following semiprime:
25195908475657893494027183240048398571429282126204032027777137836043662020707595556264018525880784406918290641249515082189298559149176184502808489120072844992687392807287776735971418347270261896375014971824691165077613379859095700097330459748808428401797429100642458691817195118746121515172654632282216869987549182422433637259085141865462043576798423387184774447920739934236584823824281198163815010674810451660377306056201619676256133844143603833904414952634432190114657544454178424020924616515723350778707749817125772467962926386356373289912154831438167899885040445364023527381951378636564391212010397122822120720357
A sufficiently large Quantum Computer that runs Shor's algorithm solves this problem in polynomial time, i.e. in hours to days.
Your classic, digital electronic super computer running the best classical algorithm (General Number Field Sieve or GNFS for short) would crunch this problem until the universe dies of heat death.
The semiprime factoring problem is a at the heart of public key encryption algorithm known as RSA. There's also another algorithm in public key cryptography called Diffie-Hellman, that relies on a problem called discrete logarithm. DH can also be solved with an algorithm closely related to Shor's algorithm.
Computers rely almost exclusively on these two problems e.g. to verify authenticity of files, software updates etc, and to establish encryption keys over insecure channels.
The modern society depends on computers for everything so understandably this is a big and important topic, and the reason NIST just recently completed a competition to find so called post-quantum algorithms that the society can rely on for the next thousand years.
danielravennest t1_j1qu2na wrote
[deleted] t1_j1t7trm wrote
[deleted]
Ill__Cheetah t1_j1miq1w wrote
Not if I can help it…
[deleted] t1_j1mr4k2 wrote
[deleted]
Thopterthallid t1_j1o1avf wrote
Can it run Minecraft with mods?
chicano32 t1_j1o1xpp wrote
Barely runs updated mods of goldeneye 64
timberwolf0122 t1_j1ocig2 wrote
But it does run all possible permutations of goldeneye at the same time
H__Dresden t1_j1n82ib wrote
Time to break the Blockchain and shut it down.
maqp2 t1_j1tpi0p wrote
The Merkle tree side won't be broken as 256-bit hash functions are not vulnerable to Grover's algorithm, and the digital signature algorithms used to sign transactions can be replaced with post quantum versions. So unfortunately we won't get rid of crypto currencies.
elefantsblue t1_j1mxls0 wrote
That’ll make it so much easier for them to run logistics on the next Holocaust. Fucking piece of shit organization needs dismantled.
fryedchiken t1_j1n28pk wrote
Tf did ibm do?
joyfield t1_j1n9loz wrote
elefantsblue t1_j1n3cs7 wrote
Google it. It’s no secret.
[deleted] t1_j1nbofm wrote
[removed]
eggybread70 t1_j1lzt18 wrote
"But can it run Crysis?" jokes aside, can anyone give this noob an idea of the practical applications of this architecture? What kind of algorithms lend itself to it, what kind of solutions will it excel at?
{Edit} changed "Far Cry" to "Crysis" to get the meme right...