Quantum computing 101

Artificial Intelligence Startups Technology Quantum Computing Innovation

Posted by Enrico on Mar 28, 2017 2220

My educated guess is that, in a couple of years’ time, quantum computers will become mainstream and this will bring massive disruption. But what are quantum computers? What are their implications? And who is working on them? I am certainly not an expert on this topic, nor do I pretend to be one, but here is my take.

What are quantum computers?

A classical computer performs operations using classical bits, which can be represented as either '0' or '1'. In contrast, quantum computers use quantum bits – called qubits – and these can be represented as '0', '1' or both at the same time. The number of classical bits required to describe the same system in the quantum world would be 2n, where ‘n’ is the number of qubits.

For example, take two particles that can have a state of '0' or '1'. We put those two particles into an algorithm represented by a black box. How many numbers do we need to describe all the different states spit out by the algorithm?

In classical computing, the result would be represented by just two numbers, since they can only be x or y but not both at the same time. So, the final solution would be one of the following combinations: 01, 00, 10, or 11. This means that we can represent the final result with just the two states: '0' and '1'.

With quantum computers, it’s slightly different, since we should take into account the entanglement of the particles. Let’s pretend we are studying a 2- qubit quantum system. As stated above, in practice, we have 2n = 22 = 4 different classical bit states. Now, let’s imagine that particle 1 always enters the algorithm represented by a black box as '0' and exits as '0'.

  • Solution A
    Particle 2 enters as '0' and exits as '0' (or enters as '1' and exits as '1'), with no influence from particle 1 (no entanglement).
     
  • Solution B
    Particle 2 enters as '1' and exits as '0' (or enters as '1' and exits as '1'), with no influence from particle 1 (no entanglement).
     
  • Solution C
    Particle 2 enters as '0' and exits as '0' (the same for 1) IF particle 1 is '0' (particles are entangled).
     
  • Solution D
    Particle 2 enters as '0' and exists as '1' (and vice versa) IF particle 1 is '1' (particles are entangled).

The fact that in quantum systems the particles could be entangled, leads to the states 00, 01, 10, 11 all being simultaneously possible solutions. We cannot anymore describe the result with only the two states '0' and '1', since the particles could be entangled. This leads to four states - 00, 01, 10, 11 - being necessary to describe our 2-qubit quantum system. This also means that our 2-qubit quantum system can interpret and analyze all four states (00, 01, 10, 11) in one operation, while a classical algorithm would need to analyze those states one at a time in four different operations to produce the same result.

In other words, a 2-classical-bit outcome can be one from among 00, 01, 10, 11 and can be described with the two states '0' and '1'. A 2-qubit system would need four states to describe the same outcome: the first state being '00', the second '01', the third '10' and the fourth '11'. A classical algorithm would need to analyze those states one at a time in four different operations to produce the same result as one operation performed with a 2-qubit quantum computer.

A 4-qubit computer would analyze 16 states in one operation, while a standard computer would need 16 operations to achieve the same result. A 6-qubit computer would analyze 64 possibilities in one operation, and so on.

Now, if we had 300 qubits, we would need 2300 numbers (or 290 numbers) to describe the system. This is more than the number of particles in the whole universe. This means that 300 qubits would contain more information than the atoms present in the universe.

It’s interesting to note that the improvement brought about by quantum computers is not in the speed of executing a single operation, but in the reduced total number of operations required to arrive at the final result.

In fact, quantum computing operations will probably always be slower than those performed with conventional computers, such as the ones required to watch videos, browse the Internet or write a document.

To achieve quantum computers, one needs to ensure the stable entanglement of the particles in the qubits, which means controlling the physical environment of the computer. At the moment, the first attempts to build quantum computers are performed in either high vacuum or extreme cold environments to avoid any background noise.

What are their applications?

The applications are multiple and difficult to foresee at this stage. Think of the scientist who invented the laser more than 50 years ago. How could he have imagined that his technology would make it possible to watch a movie from a DVD-ROM, to have eye surgery, etc.

Nonetheless, here are some major probable applications:

  1. Molecular simulations
    Caffeine – a very basic molecule – is currently the largest molecule tractable on a supercomputer. Imagine the number of applications – such as detecting the best molecules to treat cancer – that could be realized if computers were able to treat more complex molecules.
     
  2. Cryptography
    Prime factorization is a mathematical problem commonly used to secure public-key encryption systems. Finding the prime factor of a product is described by simple exponential O(exp(N) complexity. This equivalent quantum complexity would be at least in the order of O(N3).
    So, as an example, to find the prime factor of 2048 bits would take millions of years for a classical computer, while a quantum computer could do this in minutes.
     
  3. Database searches
    Think of a search through an unsorted database. The classical complexity would be O(N); the quantum complexity would be the square of it O(SQRT(N)).
    As an example, to find a specific name in a database of 100k entries, we would need an average of 50k attempts. With quantum computers, we would need only about 223 attempts, on average.

Who’s working on them?

Google is trying to combine artificial intelligence and quantum computing to optimize complex problems.

Ecommerce solutions, such as Alibaba, are working on quantum computers to develop higher security for their marketplaces.

Companies dealing with major software development are working on software verification/validation through quantum computing.

Telecommunication companies are working on real-time network traffic management and data security in the cloud through quantum computing.

Banks are exploring the use of quantum computers for real-time multi-variable financial data analytics.

Other companies, such as Fujitsu, are building customer quantum-ecrypted communications over long distances.

What are the challenges of quantum computing?

  • One of the biggest challenges is maintaining entangled and super-positioned states persistently in order to maintain the state of the memory. Similar to the early days of RAM and ROM, the main issue is the isolation of the quantum system from environmental noise.
  • Current prototypes work with a few qubits. Physicists need to be able to scale quantum processors to dozens of qubits in order to see the computational advantage of quantum computers.
  • Physicists need to be able to have reliable quantum systems without the need for extremely low temperatures and at an affordable cost.

Share this post on social media:

Contact me if you'd like to become a contributor.

  • Thumb img 2844

    Enrico Tam

    MBA, PhD, tech entrepreneur, maker

    Hi, I’m Enrico and I started hacking at 9 years old back when it was Visual Basic. After trying to become a professional tennis player I somehow got entangled in a PhD in engineering, an MBA programme and a big consulting fir... (continued)

Join the discussion

Never miss a post!

I’m Enrico, I write to learn and to share my adventures :)

Don't hesitate to write to me on twitter!

Popular bloggers

Popular posts

See all posts

Cookies help us deliver our services. By using our services, you agree to our use of cookies.