Quantum algorithms are as vital as quantum hardware in disrupting cryptography. Grasping this earlier would help.

Today, I would like to connect quantum computing algorithms with the cyber security risk that quantum computing brings. A bold line bridges these two concepts.

Understanding basic ideas behind quantum computing algorithms is essential for those looking into quantum security. I regularly get questions about how to start getting into the field. Numerous resources are available for those keen to explore quantum technology, but today, I would like to highlight two outstanding lectures by Robin Kothari — lecture 1 and lecture 2. Both offer a comprehensive introduction to quantum algorithms and include numerous references for further study. These lectures are an excellent starting point for those interested in the field. The concepts discussed by Robin will be referenced in the explanation below.

Let me briefly outline a selection of concepts about quantum computing algorithms to understand the interplay between quantum-in-cyber risk and quantum computing algorithms. 

Quantum computing can either enhance classical methods or introduce entirely new algorithms (quantum-native) that are infeasible with classical computing. In general, quantum algorithms do not replace classical algorithms but rather complement them. In some instances, classical algorithms are so efficient that quantum computing cannot provide any speed advantage, for example, in algorithms implementing simple mathematical operations (like multiplication) or probability amplification algorithms. However, in some cases, quantum computers significantly outperform their classical counterparts. 

Algorithms often consist of building blocks that could include a mix of quantum-native, purely classical or quantum-enhanced classical algorithmic blocks. Some blocks aim to address a business problem of interest (notably Shor's algorithm in cryptography), but many serve smaller purposes to make the whole algorithm workable, like Amplitude amplification, which serves as fundamental components rather than standalone solutions. 

The enhancements from quantum algorithms vary widely, from minimal to exponential. 

• The speed-up is called "exponential" when the size of the problem increases, but the time it takes to solve the problem using a novel method grows much more slowly compared to an old method. In some cases, a problem that might take a classical computer an exponentially longer time to solve (like doubling the time with every additional piece of data) could be handled by a quantum computer in a relatively fixed amount of time, even as more data is added. Algorithms that offer exponential speed-up allow us to tackle problems that classically could not be solved. These algorithms are rare and are of the most interest. Examples include Shor's algorithm or the Deutsch-Jozsa algorithm. Other examples can be found here.

• Another level of improvement is "polynomial speed-up". Polynomial speed-up refers to a situation where a quantum computing algorithm can solve a problem faster than a classical algorithm, but the improvement in speed increases by a factor that can be described by a polynomial function (like n squared). Unlike exponential speed-up, where the improvement massively increases as the size of the problem grows, polynomial speed-up offers a more moderate but still significant improvement. The most famous examples are Grover's search algorithm or algorithms for solving linear systems of equations. Other examples can be found here.

• The next possible speed-up is a speed-up over some constant. In this case, we are referring to an improvement in performance where an algorithm completes a task faster than another by a fixed amount. This constant doesn't depend on the size of the input; it's a straightforward multiplier indicating how many times faster one method is compared to another. This is the least preferable outcome; sometimes, it is not considered a speed-up.

• The last possible outcome (not a speed-up) is an advantage in a heuristic algorithm. A heuristic algorithm is a problem-solving method that uses practical shortcuts and approximations. Heuristics don't guarantee a solution to the problem, but they work most of the time. 

It's important to note that even algorithms providing exponential speed-ups may be limited by other steps in a program that negate these advantages. Two particular challenges in quantum computing include data loading and error mitigation. 

Media coverage frequently emphasizes algorithms with exponential speed-ups due to their significant impact. Given the current and near-future cost of quantum computing, it is understandable that exponential speed-up is the proper focus. However, as quantum computing becomes more affordable, other speed-up types could also play crucial roles. In cyber security, where lead time to remediation is measured in years, early recognition of these possibilities becomes strategically important.

Shor's algorithm is famous for breaking RSA and Diffie-Hellman cryptosystems, including versions that use elliptic curves. Beyond Shor's algorithm, researchers are developing many quantum algorithms aimed at attacking different cryptosystems. These attacks fall into three main categories:

1. Quantum algorithms that break cryptosystems in polynomial or sub-exponential time. These algorithms can break certain elliptic curve-based cryptosystems faster than traditional methods but not as fast as Shor's algorithm.

2. Quantum algorithms that improve classical attacks on cryptosystems by speeding up parts of these attacks. This includes using Grover's search and quantum collision finding as algorithmic blocks in wider cryptoanalysis techniques. These improvements may not break the cryptographic scheme but may affect how cryptographic keys are chosen and used, as they can make some keys more vulnerable than others.

3. Attacks using quantum superposition queries to challenge block ciphers. The basic idea is to prepare the quantum state that represents the block cypher and querry it over all possible inputs (hello superposition) to break the system. While these attacks can be very effective, making such queries is often impractical in real-world scenarios.

Please check the Quantum Cryptanalysis block at https://quantumalgorithmzoo.org for references and further links.

Two key insights arise from this discussion, one relating to cybersecurity and the other to industry practices.

Firstly, the viability of current cryptographic algorithms hinges on more than just advances in hardware; it is equally influenced by the progression of quantum algorithms. Both renowned and lesser-known algorithms play a critical role in shaping the future of this field.

Secondly, forming a team for a quantum computing initiative requires a profound understanding of both classical and quantum algorithms. Designers of quantum algorithms need to be well-versed in classical routines to strategically select the most effective approach, balancing between traditional and quantum techniques to optimize performance. This specialized expertise is rare, making the field highly competitive for skilled professionals.