# Do quantum computing principles have a theoretical or hypothetical potential to solve factorial time problems?

I neither have a background in QC, higher mathematics (calculus) and nor have I gone through the literature about the field. As a layman what catches my attention is that people say that quantum computers might crack state of the art encryption algorithms, which are as of now publicly known to be uncrackable because traditional computers require awful lot of time to crack them (of the order of tens of thousands of years), which indicates that the number of procedural ops required to get the answer explodes to a very large number and these ops probably do not turn out to be very easily parallelizable. SOF experts say that Quantum Computing is useful because:

Where quantum computing provides a massive benefit is where there's some symmetry or periodicity that can be used to make undesired outputs cancel each other out. For example, Shor's algorithm takes a superposition of classical inputs {x}, evaluates f(x) = a^x mod N on each x (where a is random and N is a number we'd like to factor), then applies a Quantum Fourier Transform which destructively interferes the undesired outputs and constructively interferes the correct ones so that when you do make your single measurement before collapsing the state, you're very likely to get a useful answer.

Factorial time problem here imply problems or algorithms which have worst case run times that are proportional to O(n!) (ex: travelling salesperson problem).

## 1 Answer

There are problems for which quantum computing provides an exponential speedup. As you correctly stated, a prominent example is factorization. However, the speedup heavily depends on the kind of problem. For example, Grover's algorithm for unstructured search only provides a quadratic speedup. Therefore, it is hard to a priori say which problems can be efficiently solved by quantum computing.

In general, you want a problem with a low input size (to load the data) and a low output size (to read out the data). The complexity of a problem could, for instance, originate from combinatorial complexity (some of which have factorial complexity). So in a sense, you have a point.

To break RSA encryption, much bigger, error-corrected quantum computers are necessary, which would take millions of physical qubits. IBM just released a quantum computer with a 1,121-qubit processor (not error-corrected), and in a recent paper, a 48-logical-qubit quantum computer was presented. So there is still a long way to go until RSA encryption can be broken.

The first relevant use cases for a quantum computer will most likely be quantum chemistry/physics-related, specific optimization tasks, or sampling problems. This is not a comprehensive list, but rather a collection of possible near-term use cases. It is estimated that with a couple of hundred logical qubits and enough error-free operations on these qubits, quantum chemistry applications could be tackled. I hope this answers your question.

• What are some problems of great interest pertaining to quantum physics and chemistry which can make a difference in our day to day lives. Dec 13, 2023 at 17:58
• Take for instance drug development. With better force fields (obtained using quantum chemistry) you’ll be able to predict the behaviour of molecules with higher accuracy. With that you can predict which candidate molecule is the better drug. This is HUGE, as big pharma spends billions of dollars on that. Another example would be predicting properties of materials, e.g. for batteries.
– Lars
Dec 13, 2023 at 19:01
• That sounds like some of the very important problems to be solved. Dec 14, 2023 at 9:18
• Could you throw some more light on low "input, output" size? Does this mean the number of bits/qubits needed to be allocated for storing the input, output data? Also, if you have a higher number of physical qubits in a quantum computer, can it tackle the combinatorial complexity? Because many problems in Boolean algebra become unsolvable because of combinatorial complexity, those might become solvable. Dec 18, 2023 at 6:28