Quantum computers
1 √2
1 √2
−
(
)
(
)
1 √2
1 √2
−
The same classical probabilities
This example is contrived but its efficiency also applies to the generalized form, the Deutsch-Josza algorithm: 19 given an input string of 𝑛 bits, a function returns the single value 0 or 1. The function either returns the same value for all strings (constant) or returns 0 for half of all input strings, and 1 for the other half (balanced). It is necessary to find out whether the function is constant or balanced. The best classical outcome giving a 100% certain result could require two tests but may need up to half + 1 of the 2 𝑛 possible input strings . The quantum algorithm needs only one test: a constant oracle doesn’t modify any bits; a balanced oracle negates half the bits. 20 This is an enormous speed-up. Inspired by a variant of the Deutsch- Josza algorithm, Shor’s quantum algorithm efficiently fa ctorizes an integer 𝑛 , where 𝑛 = 𝑝 × 𝑞 . 21 Internet security uses encryption algorithms, such as RSA, that rely on such factorization s being too long to solve. With Shor’s algorithm, a billion -qubit computer could factorize a 2000-bit integer in ‘ just over a day ’ , as reported by Montanaro. 22 This is compared with ‘ hundreds of modern computers ’ taking over 2 years to factorize a 768-bit integer. Therefore, this algorithm illustrates the advantage that quantum computers have in specific problems. Grover’s quantum algorithm drastically outperforms classical unstructured search algorithms for finding a given element in a list. 23 It takes an average time proportional to √𝑛 where 𝑛 is the number of elements in the list, improving the classical time proportional to 𝑛 2 . It uses amplitude amplification – the target element in the list has its amplitude iteratively increased whilst the other elements have their amplitudes decreased. Th is technique is also employed in other quantum algorithms. Grover’s algorithm allows databases to be sorted through more efficiently. Quantum computers are also set to solve other challenging search and optimization problems faced by businesses. 24 Quantum computers look to be useful in problems simulating other quantum mechanical systems, such as in finding chemical bond lengths. Classical computers take a long time to simulate all the quantum states of a system, but a quantum computer could model a variety of quantum systems more directly. 25 Quantum computers will make a difference, but there are still technical challenges to overcome. Shor’s algorithmhas been demonstrated to factorize the number 15 on a 7-qubit computer, 26 but the best gate- based quantum computers still only use around 50 qubits, limiting problem size. Classical supercomputers can simulate the same number of qubits, even if they take longer to do so. 27 Scaling up
19 Helwer (2018). 20 Deutsch-Josza Algorithm (Undated). 21 Montanaro (2016). 22 Montanaro (2016). 23 Grover’s Algorithm (Undated). 24 The Future of Quantum Computing (2019). 25 What is quantum computing? (2019). 26 Bonsor and Strickland (2000). 27 Crane (2020).
179
Made with FlippingBook Digital Publishing Software