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

CNC Blockchain Advisory – Helping Companies Make the Quantum Leap to Decentralized Operations

Blockchain and decentralized applications have taken the world by storm, with industries as diverse as governance, agriculture, healthcare, finance, education, and transportation benefitting from this new technology. Thanks to their in-built protocols that ensure immutability, security, efficiency, and privacy, adopting a decentralized, blockchain-based approach to business presents immense opportunities for streamlining processes and operations. However, this only holds true if companies are able to get their blockchain implementations correct. According to Deloitte Consulting, blockchain implementation is more about business process change and less about the technology itself. Despite this, however, too many companies come up short when trying to address blockchain implementation issues, including: Overcoming resistance to change from within the organizationHandling usage complications Operating in an environment that lacks regulation Slow onboarding A lack of access to specialized knowledge Lack of a primary application that can be used across the organization The cryptocurrency boom of 2017 was a double-edged sword. While it opened the gates to funding and growth for the crypto and blockchain industries, the crypto crash and ensuing winter of 2018 made it painfully clear how important regulation, processes, and a standardized approach are to blockchain adoption and implementation. This is where CNC Blockchain comes in. CNC Blockchain is a consulting and advisory company that helps organizations understand blockchain technology. From assessing the impacts it will have on the organization to delivering applications, processes, and ancillary services, CNC Blockchain helps clients understand how and when they should adopt blockchain in their organizations, how to collaborate with other players in the industry, and how to effectively roll out a comprehensive blockchain-based technology revamp. CNC Blockchain specializes in providing companies with time-critical and industry-specific insights to help them make strategic decisions to move forward with their blockchain adoption and has presented at high-level tech summits and conferences educating companies and governments on the importance and benefits of decentralized ledger technology (DLT) in the business ecosystems of the future. Two interesting areas that blockchain has already seen substantial progress in are the use of smart contracts to eliminate middlemen, and the use of secure medical records to provide countless millions with comprehensive health records wherever they go. Successful pilot projects in countries as far and wide as Australia and Estonia have also proven that it does work– but only with the right resources and guidance along the way. CNC Blockchain recently presented at the Blockchain Tech World Conference on March 13 and discussed why senior leadership teams need to prepare early for blockchain. It also spoke on a panel on cybersecurity innovation that discussed blockchain exploration and other considerations for healthcare. With industry experts in the fields of healthcare, commerce, technology adoption, data science, and leadership, CNC Blockchain continues to meet with and educate major players in the security and healthcare spaces on how blockchain can and will bring about a global revolution in efficiency, transparency, security, and privacy. Although there is still significant resistance to change and skepticism in legacy industries when it comes to this new technology, we have only begun to scratch the surface of what blockchain can do. CNC Blockchain has been able to gradually bring many new players into the fold by educating them on the benefits of blockchain and making it clear to them just how much they will benefit from adopting a comprehensive and well-thought-out blockchain strategy. With the efforts of CNC Blockchain and others in this industry, it is only a matter of time before we see Blockchain 2.0 in common use the world over – and the revolution starts today. John Riley III, CEO, CNC Blockchain Advisory at Blockchain Technology World Conference, March 13 2019 The post CNC Blockchain Advisory – Helping Companies Make the Quantum Leap to Decentralized Operations appeared first on Bitcoin Garden.
Bitcoin Garden

Quantum Computing and Blockchain Transparency May Not Fare Well for Bitcoin Whales: IBM VP

The vice president of blockchain and digital currencies at IBM says that quantum computing poses a real near-term threat to digital assets such as Bitcoin (BTC) and Ethereum (ETH). Lund said this in a recent interview with Fred Schebesta of at IBM Think 2019. Quantum Computing: A Risk for Digital Assets? Virtual currencies are […]
Bitcoin Exchange Guide

Hot news

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