"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...

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).

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.

IIRC they are super useful for financial number crunching and forecasting.

>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?

Factoring prime numbers

Cracking bitcoin

Breaking encryption.

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.

Thanks, nerd bros.

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.

Not if I can help it…

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.

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.

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.

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.

[deleted]

Can it run Shor's algorithm? What's the largest number they've been able to factor?

Creating holographic wormholes.

Physicists Create a Holographic Wormhole Using a Quantum Computer

[deleted]

> 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.

That’ll make it so much easier for them to run logistics on the next Holocaust. Fucking piece of shit organization needs dismantled.

Primarily just quantum benchmarks and academic uses. Those toys are still years from being even remotely useful for real-world, practical calculations.

will this be used for machine learning at all? can these computers do the linear algebra used in machine learning?

Tf did ibm do?

Google it. It’s no secret.

IBM, there's a company that should be Microsoft's equal yet rarely hear of it.

I feel like AI will eventually be something that really takes off thanks to QPUs.

Time to break the Blockchain and shut it down.

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.

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.

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

https://en.wikipedia.org/wiki/IBM_and_the_Holocaust

https://www.qusecure.com/aes-256-is-quantum-resistant-capable-of-withstanding-brute-force-attack/#:~:text=With%20quantum%20computing%20quickly%20becoming,is%20only%20expected%20to%20achieve

[removed]

Okay, now explain it to me like I am five?

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.

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?

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.

Quantum chips will solve some math problems faster than normal computers. It is unlikely these chips will be used to run computer games.

“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

No, it won't. ML applications of anything quantum are extremely limited, especially in this regime of qubit numbers.

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!

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

is held karp an approximation or does it solve it fully?

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

That was a blast from 2004.

Totally. Just to be clear for the thread, a useful quantum computer will break ECC way, way before AES or SHA2.

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.

How the hell says fry cry? It’s either doom or crysis.

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.

Oops. I fucked up. You're right, it should be Crysis.

What I do wonder tho is, how will all these investment return itself? I can’t imagine a good business case for now…

So you're saying that there might one day be a quantum computer that can only run crisis extremely well?

> 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.

Yeah, BQP (the problem class solved by quantum computers) is generally believed to be disjunct from NPC.

Ah yes, because BMW and Mitsubishi are still the exact same companies that they were 80 years ago. No change whatsoever, no sir. It’s not like people, companies, and countries can have massive change over several generations.

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

> 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.

> 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.

[deleted]

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.

> 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.

Different business models lead to different outcomes.

Can it run Minecraft with mods?

Barely runs updated mods of goldeneye 64

But it does run all possible permutations of goldeneye at the same time

Are quantum processors only good for one calculation since all the qubits are collapsed afterwards?

Technically then AES is "broken" using conventional means but only barely.

I wouldn't be surprised if the DOD already has it.

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.

Which mode of operation?

Wasn’t Qubit that weird video game from the 90’s with the big nose???

For reference; the earth is about 2^92 grams.

They are waiting for bios update and then watching the forums for posts by early adopters before proceeding.

https://en.m.wikipedia.org/wiki/Biclique_attack

Can it solve the mystery of why my brain doesn’t make dopamine? If not it’s useless to me.

Did they ever solve the EC issues with quantum?

Does this mean that quantum computers could handle redundant loads in massive proportions?

I’m thinking replacing servers and such.

That’s a theoretical attack (not practical) and it looks like it’s only applicable to ECB mode, not something like CBC or GCM

Noob question but if I had 7 1000q-bit QCs could I break this encryption?

There are five people on Reddit who really know what a Qubit is, and I am one one of them.

Close but no. It was Qbert.

https://en.wikipedia.org/wiki/Q*bert

And it still can't run Adobe Premiere smoothly.

Do you think it would be possible to use the net with these things?

One can only imagine tho what sorts of games these would have in future...

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

[deleted]

pretty much anything that current tech can do efficiently, is not a problem a quantum computer can, and vice versa.

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

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?

And then the angels start talking to you

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.

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.

Isn't any attack that we don't have the computational power to test going to be theoretical?

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.

[deleted]

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.

Also, SHA256 does lossy compression, and obtaining preimages larger than 256 bits can not be done at all, QC or not.

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.

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.

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.

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.

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.

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.