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!

8

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.

15

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.

5

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.

18

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.

26

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.

118