What are quantum computers good for?

Forget cracking crypto, think modelling reality itself to help build a better one

Security for virtualized datacentres

The compiler

There’s another reason to have a classical computer act as the intermediary between the user and the quantum computer: it makes the quantum computer more flexible, because it will carry out a step analogous to a compiler in conventional computing.

The compiler’s job is to take the user’s program instructions, and determine things like the algorithm the program will use, and which quantum operators – qubit gates – are needed to execute the algorithm.

Constant vs balanced?

To make quantum computers useful, we need to understand when they will clearly outperform classical algorithms – which is hard to explain convincingly, but lets try a simple example.

Let’s imagine a (rather pointless) guessing game: Alice has two machines in front of her, comprising a keypad and a display that can show 0 or 1, and it’s her job to figure out which one is working correctly. The machines will accept any input between 1 and 1000 (decimal, not binary), and should display a 0 for 500 of the possible inputs, and a 1 for the other 500 – except that Alice doesn’t know which inputs produce which results. All she is told is this:

“The faulty machine only displays 1, never 0”.

The question is: is there an efficient way to test the machines? Alice could simply grab one of the machines, and start punching in numbers. If Alice chose the working machine, and if the association between numbers and 0 or 1 outputs is randomly distributed, she could find an answer fairly quickly that way.

If she’s lucky.

If she’s unlucky, Alice might have to test 500 numbers on one machine before she sees the output change from 0 to 1 (or vice versa). Similarly, if she’s unlucky, she chose the broken machine, and she will have to test 500 inputs to be certain.

Mathematically, what Alice is trying to do is work out whether the unknown function – the one inside the working machine – is constant or balanced. Computers can work this out – but the best known classical algorithm still gives us a worst-case complexity in which the required tests are always half the possible number of inputs. If the machines accepted numbers between 1 and 2000, then 1000 tests are needed in the worst case.

In one of the earliest breakthroughs in quantum computing, Deutsch and Jozsa devised a simple quantum algorithm for solving this problem. They discovered that if you had a quantum version these gadgets, one which could have quantum bits as inputs and outputs, then this problem could be solved by a single query.

The key to this quantum advantage is that much of the work that Alice would have performed can be taken care of by quantum superpositions and interference.

This algorithm is initialized by setting the input qubits and output qubit to 000…0.

Then we apply some quantum gates that create a superposition over all possible inputs to the gadget. There is then a circuit element that feeds these inputs into the unknown gadget. Finally, the same operation that created the superposition over all inputs is performed once again and all the qubits are measured.

Before we perform this measurement, the computation is in Schroedinger’s Box (to borrow a metaphor) and qubits exist in a superposition of 0’s and 1’s. When we “open the box” and destroy the superposition we will simply read out a string of 1’s and 0’s.

Now, because of the way in which this circuit is implemented, if the gadget was defective, that is, constant, then it will always give the answer 000…0 with 100 percent. If the gadget was balanced – that is, not defective – then some of those output bits will definitely give the answer 1. For the working machine, there is 0 percent chance that we will read out a string of 0’s.

Next: getting more complex

Remote control for virtualized desktops

More from The Register

next story
Voyager 1 now EIGHTEEN LIGHT HOURS from home
Almost 20 BEEELION kilometres from Sol
Ex-Soviet engines fingered after Antares ROCKET launch BLAST
Speculation rife, but Orbital claims it's too early to tell
MEN: For pity's sake SLEEP with LOTS of WOMEN - and avoid Prostate Cancer
And, um, don't sleep with other men. If that's what worries you
Jim Beam me up, Scotty! WHISKY from SPAAACE returns to Earth
They're insured for $1m, before you thirsty folks make plans
Er, we think our ISS launch beats your fishing expedition
NASA: Spacecraft crash site FOUND ON MOON RIM
'What fun!' exlaims NASA boffin who found the LADEE
Comet Siding Spring revealed as flying molehill
Hiding from this space pimple isn't going to do humanity's reputation any good
BAE points electromagnetic projectile at US Army
Railguns for 'Future fighting vehicle'
prev story


Why and how to choose the right cloud vendor
The benefits of cloud-based storage in your processes. Eliminate onsite, disk-based backup and archiving in favor of cloud-based data protection.
A strategic approach to identity relationship management
ForgeRock commissioned Forrester to evaluate companies’ IAM practices and requirements when it comes to customer-facing scenarios versus employee-facing ones.
High Performance for All
While HPC is not new, it has traditionally been seen as a specialist area – is it now geared up to meet more mainstream requirements?
Top 5 reasons to deploy VMware with Tegile
Data demand and the rise of virtualization is challenging IT teams to deliver storage performance, scalability and capacity that can keep up, while maximizing efficiency.
Mitigating web security risk with SSL certificates
Web-based systems are essential tools for running business processes and delivering services to customers.