One Step Closer to Post-quantum World

One Step Closer to Post-quantum World

Urmila Mahadev, a graduate student at UC Berkeley, has come up with a solution to a major problem in quantum computation. She has found a way, using only classical computers, to know whether a quantum computer precisely follows given instructions

Intro to quantum computers

A computer is a machine that does calculations. Whether you are watching a Youtube video, writing an essay or playing a game, all your computer does is just add, subtract, multiply and divide numbers. Your computer does these calculations with the help of small electrical parts called transistors that act as switches. These switches are combined into logic gates, and logic gates in turn are connected to each other to form adding, subtracting, multiplying, and dividing mechanisms.

In our normal world, switches can be either on or off, electricity is either flowing through the circuit or not. We sometimes hear that computers work only with 0s and 1s because they store information of switches being off and on in bits that can be either 0 or 1 at one point in time. In the world of quantum physics, however, it is not that simple. A quantum object can actually be in different states at the same time or, more scientifically, the object can be is a superposition of different states. A famous example of a quantum object is Schrödinger's cat. This cat lives in a closed box. Inside that box there is also a deadly mechanism that may or may not activate. And until you, an outside observer, open that box, the cat is dead and alive at the same time. This cat is in the superposition of being dead and alive.

Quantum computers use quantum bits, or qubits. Qubits are quantum objects, usually electrons of atoms, that are spinning chaotically in each and every direction at the same time! If this is hard for you to grasp, do not worry. As some physicists say, 'It’s not that you understand it, you just get used to it'. So when qubits are spinning in all directions, we can think of them as rapidly alternating between 0 and 1. This along with a number of other curious properties such as entanglement of quantum objects are harnessed by special complex machines called quantum computers to conduct efficient calculations. Quantum computers may bring us closer to discovering the secrets of the universe by, for example, simulating black holes and protein folding, which are very computation-heavy operations.

Problem with quantum computers

The major problem with quantum computation is that we do not know how to check whether a quantum computer did all the instructed calculations or even generated the correct result. With classical computers this is really easy — all you need to do is check every step, you check every time a bit is 0 or 1. Quantum computation, however, does not have steps because it performs all steps at the same time and stops the moment you measure the result. Again, you cannot know whether the cat is dead or alive, until you open the box. Similarly, you cannot see whether the qubit is 0 or 1 without measuring it. Measurement collapses the superposition into a single unambiguous state. So, in a way, a quantum computer is a quantum computer only when you don’t look at it. As soon as you look at the qubits, they become classical bits. So if you cannot follow the process of computation, how do you know if the computation was correct?

Proposed Solution

Urmila Mahadev proposes a solution that predicates on a simple idea that if a quantum computer can do something that classical one can’t, we can still use classical means to check the result. As such we can construct such a function that is very hard to compute but is easy to verify, a trapdoor function.

For example, it is believed that quantum computers are really good at factoring numbers. For classical computers given a large number it is incredibly difficult to find its factors. This is the biggest pillar of modern cryptography. It takes a big number, a private key, multiplies it by another big number and outputs the third even bigger number, the public key. You can feed this public key to a computer but it will take hundreds of years to find its factors. But if a quantum computer does in fact find these factors, we can simply check the result by multiplying the generated numbers, which any classical computer can do. To illustrate we will use smaller numbers. We can have the quantum computer find factors of 2047 and when it gives 23 and 89, we can simply multiply those to verify the result.

Urmila Mahadev has come up with an interactive protocol that allows classical computers to verify quantum computation. They can do it by having the quantum computer measure its own qubits and output the result. For a while, the problem with this was the fact we could not trust the computer because we could not tell which superposition of superpositions the computer measured. Urmila implements the trapdoor function to first generate the output of a certain superposition and verify if qubit measurement belongs to that superposition.

Urmila approaches this problem using cryptography known as Learning with Errors cryptography which is a topic for another article. But nevertheless this is a big discovery that once again proves the sheer power of cryptography and prepares us for the post-quantum world.

Related news

Google Claims That They Have Reached Quantum Supremacy

Coinspeaker Google Claims That They Have Reached Quantum SupremacyEver since Google announced that they are working on a Quantum super-computer the world has been eager to see the results of such a scientific and technological breakthrough. Last year in March, they presented the super-computer which boasted a 72-qubit computing power. Since then the word quantum computing has become very popular and nations around the world cannot wait to get their hands on this remarkable discovery. But why?The main reasons might be the fact that quantum computing can solve issues ranging from artificial intelligence (AI) to even healthcare and drug development. But while others are only dreaming about it, Google is making these dreams reality. Now they are proud enough that they can declare that they have reached “Quantum Supremacy”.When trying to describe what Quantum Computing is, the very short definition would be – a very tremendous computing power. Basically, while today we know that all the computers are using the binary code, or binary bits, which consists of 0’s and 1’s, then Google’s Quantum Computer uses a completely different processing power approach, using qubits. These qubits can be connected in a group in a way that allows for significantly more processing power than the same with binary bits.Many experts say that Google Super-computer is way more powerful than some of the world’s super-computers. They even did a test where they put Google’s super-computer and IBM‘s Summit, which is commercially known as the world’s most powerful computer, to complete a calculation. The results of this test were astonishing. While IBM’s Summit would’ve completed this task in about 10,000 years, Google’s super-computer solved the calculation in 3 minutes.“To our knowledge, this experiment marks the first computation that can only be performed on a quantum processor,” stated Google researchers.Google described the achievement as a “milestone towards full-scale quantum computing.”So What Does This Google’s Quantum Supremacy Mean For Blockchain?One of the main topics, when speaking about quantum computing and crypto or blockchain in the same sentence, is about the fear that these super-computers could potentially threaten all well-known encryption algorithms, for example, Bitcoin. That is why many blockchain developers are talking about quantum-resistant blockchains. While some are talking, others are doing. For example, QANplatform already has developed a quantum-resistant blockchain called QAN.“The most popular public-key algorithms are theoretically at risk of being broken by a quantum computing breakthrough. Most encrypted data intercepted and stored today could be decrypted by quantum computers in the near future,” the CTO, Johann Polecsak commented.However, he also says that while this all sounds very dramatic, the reality is that “it’s hard to gauge the significance at this time,” he adds.But not all are so optimistic. Andrew Yang, the pro-tech Presidential candidate, expresses his concern about the new technology and encryption standards as such:“Quantum computers, using qubits, will theoretically be able to perform the calculations necessary to break our current encryptions standards in under a day. When that happens, all of our encrypted data will be vulnerable. That means our businesses, communications channels, and banking and national security systems may be accessible.”However, in reality, the current cryptographic encryption standards are actually really high, says Chris Pacia from Openbazaar. He writes:“If every one of the 7 billion people on Earth had 10 computers testing 1 billion key combinations per second, it would take the entire population 77,000,000,000,000,000,000,000,000 years to find a single 128-bit AES key.”In case of something going wrong – we would just need to switch to a different Encryption Standard. That also applies to Bitcoin. If a quantum computer would try to crack the SHA-256, the obvious solution would be to switch to a stronger encryption algorithm of the same family – SHA-512.The conclusion is that this still is very early to judge, but at the moment, it still is science fiction, which wouldn’t have many practical applications in the world which we know now. Google Claims That They Have Reached Quantum Supremacy
Coinspeaker

What Google’s Quantum Supremacy Means For Cryptocurrency

The threat of quantum computing has long loomed over classical cryptography which provides the security behind most current blockchain networks. Search giant Google recently claimed it has reached a milestone in quantum computing which could have serious implications for cryptocurrency. Does it Pose a Real Threat to Cryptocurrency? In a new scientific publication, tech giant Google claims to have reached ‘quantum supremacy’ with a 53-qubit quantum computer. This definition means that the machine has solved a problem that no classical computer could solve within a reasonable timeframe. The implications of this could be so far reaching that NASA removed the paper which it had originally published here. It has been reproduced here in a partially readable format. According to reports, the new quantum processor took just 200 seconds to complete a task that would normally take thousands of years for a regular supercomputer to do. Google researchers wrote “To our knowledge, this experiment marks the first computation that can only be performed on a quantum processor,” In theory this means that the computer could break 53 bit cryptography in seconds. Breaking Bitcoin? Bitcoin’s cryptography is currently 256 bit encryption (SHA-256) while Elliptical Curve Digital Signature Algorithm (ECDSA) is used in to create private and public key pairs. It will be a while yet before any computer, quantum or otherwise, can crack this but scientists at the search firm estimate it may be possible in the next few years. The report added that the number of qubits, the basic unit of quantum information in a two-state quantum mechanical system, could double at least every year. This would outpace Moore’s Law and give the company a computer capable of breaking military encryption by 2024. An increase to SHA-512 or stronger encryption algorithms would prevent the search giant ‘breaking cryptocurrency’ within the next decade but essentially the technology needs to evolve to maintain its security. There are already a number of quantum resistant blockchains in existence so the FUD headlines are really just that. Bitcoin is not about to be broken by Google. A more concerning notion is the growing power that this company has. Google already dominates data flows across the planet and practically dictates what makes it into the news and what doesn’t. It is the grand overseer of the internet and operates with virtual impunity. The company that said ‘don’t be evil’ is already more powerful than most governments and with quantum computing technology at its fingertips, no piece of data on the planet will be safe. Will Google take over the world with its quantum computers? Add your thoughts below. Images via Shutterstock The post What Google’s Quantum Supremacy Means For Cryptocurrency appeared first on Bitcoinist.com.
Bitcoinist

Hot news

By continuing to browse, you agree to the use of cookies. Read Privacy Policy to know more or withdraw your consent.