Quantum computing offers the hope of dramatic increases in computational capabilities. That’s the promise of quantum computers that can handle hundreds of thousands or millions of quantum bits or qubits.
But for the moment, the state-of-the-art machines barely manage a few dozen qubits and cannot yet outperform classical computers in any meaningful way. Part of the problem is that quantum algorithms generally require hundreds or thousands of qubits, even for simple problems. So mathematicians and computer scientists are desperately searching for more elegant algorithms that depend on fewer qubits.
Enter Kapil Goswami and colleagues at the University of Hamburg in Germany who have found a way to solve the travelling salesperson problem using a single qubit. They say the approach could be applied to other problems and has the potential to transform the way computer scientists think about quantum algorithms.
The Travelling Salesperson Problem a combinatorial optimization problem and one ...
