Sun May 17 2020
Quantum Computing, the dream of every techy, just took a huge step closer
Quantum Computing promises us that it could help solve some of the most complex challenges currently facing our planet. Tackling global problems like climate change could, potentially, take a conventional computer, no matter how fast, billions of years to model and solve, offering a solution long after it could possibly be helpful.
The promise of Quantum Computing however is that it could arrive at the same solution in weeks, days or even hours!
This increased pace of computing power is being developed by researchers; currently calculating algorithms that will be able to harness the immense (and spooky) properties of quantum mechanics, superposition and entanglement to be precise, to process incredibly complex calculations on tooled-up quantum hardware.
In preparation for this exciting quantum leap (sorry – we couldn’t help ourselves!) in computing, researchers have been trying to identify and classify problems that will be best suited for quantum computing and exactly what kind of speed-up in calculation power could be expected; whether it would be polynomial or exponential.
Take Shor’s algorithm for instance.
It’s a famous quantum algorithm that is known will yield exponential speedups on a quantum enabled computer. Understanding that has already had untold benefits on the cyber-security industry, helping shape how we both encrypt and protect sensitive data.
But… the impact quantum computing might have on more common types of problems has, until now, been a mystery.
Robin Kothari, a Senior Researcher on the Microsoft Quantum Systems team, alongside fellow researchers Scott Aaronson, Shalev Ben-David, and Avishay Talhave made a breakthrough in two common problems that have puzzled researchers for over twenty years; resolving conjecture about the speedup that is obtainable by quantum algorithms over classical algorithms.
The ‘problems’ the team decided to explore where ones that can be found in almost every sector or organisation, that of the best way to analyse the massive sets of unstructured data routinely produced now a days whilst being able to understand it’s connections and patterns within a large network.
They were able to show that the best possible speedup would be quartic for unstructured problems in quantum query complexity.
This disapproved the previously held assertion, arrived at in 1981, that at best, a sixth power speedup would be possible.
By definitively answering the question of the largest possible quantum speedup for these problems, the team has enabled fellow researchers and organizations across the industry to better understand both the opportunities and limits of these algorithms and to continue focusing on problems that hold promise for future quantum impact.
Interested in what bleeding edge software engineering could do for your organisation? You know what to do...
Sun May 17 2020