As you all know, quantum physics is much more complicated than classical physics, so there is no fixed place for accuracy in quantum mechanics, so the idea of quantum algorithms that scientists have to come up with is just a fantasy. Which was introduced as bogosort.
What is Quantum Bogosort Algorithm?
Quantum bogosort is a hypothetical sorting algorithm based on bogosort, created as a joke among computer scientists. The basis of this is the multi-universe interpretation of quantum mechanics. The quantum bogosort algorithm generates a random permutation of its inputs, checks that the list is sorted, and if it is not, destroys the universe. Assuming that the many-worlds interpretation is correct, the use of this algorithm would result in the existence of exactly one living universe where the inputs are successfully sorted.
Quantum mechanics has conceptualized an explanation of the infinite universe, according to which there exist multiple universes parallel to space and time, and on this basis has developed this hypothetical quantum algorithm that sorts lists on the explanation of the existing infinite universe.
understand some steps
Make the list quantum random, such that there is no way to know what order the list is in until it is looked at. This would divide the universe into O(n!) universes; However, segmentation has no cost, as it happens continuously anyway.
If the list is not sorted, destroy the universe. (This operation is left as an exercise for the reader.)
All the rest of the universe consists of lists that are sorted.
What experts say on quantum algorithms
Experts believe that it is really difficult to find new quantum algorithms. Arguably some techniques have been discovered for building quantum algorithms. These include period-finding, which can find periods of sequences that can be exponentially long; Grover’s search algorithm, where quantum computers can search a set of n objects and find one with the desired properties without taking the time to look at each object (only the square root of n of them); Some operations on matrices and vectors can be performed more efficiently on a quantum computer; And quantum mechanical systems can be efficiently simulated on a quantum computer.
So if you have a problem that you want to solve on a quantum computer, and you want to do it significantly faster than on a classical computer, the first thing you do is to see if a known technique works. If none of them do, you’ll have to look for a newer technology.
Any new technology for solving problems on a quantum computer will be a major discovery, so it looks like you won’t find one. In the past two decades many people have been looking for new quantum algorithmic techniques, and very few of them have actually been found.
There is a technical problem with this. Because we don’t have really big quantum computers right now, so you need to provide mathematical proofs to demonstrate that a new algorithm works efficiently.
If you look at the history of classical computation, many efficient classical algorithms were discovered – someone programmed them on a computer and found that they worked well by testing them, and it was only later that theorists proved that they worked well. worked from.
So we can expect the same thing to happen with quantum computers: many useful algorithms will be discovered by experiments on quantum computers, and we will discover more techniques to build quantum algorithms in this way. However, we first need to wait until quantum computers are powerful enough to test the algorithms.
In the above information we already have an algorithm available as quantum bogosort algorithm, but no one knows how to prove that they work well, or whether their running time is reasonable. It appears that only by testing them experimentally can we find out whether these bogosort quantum algorithms are useful.