Does this quantum algorithm to check for a permuting function make sense? [closed]

Question

Even "Deutsch's algorithm" seems too difficult. Maybe I found an algorithm that is more appropriate for people without knowledge.

Less to explain. Easy to understand. Or do you have something better than the following?

Problem: Check whether a function permutes on a given set of values.

Example:

This function does permute: F: {0,9,10,12} -> {10,0,12,9}

This function doesn't permute: F: {0,9,10,12} -> {10,0,12,13}

Classically, we would calculate each of the n elements individually, and compare the result set with the original set: F(0)=10, F(9)=0, F(10)=12, F(12)=9

So n-steps are needed. Both for calculating and for comparing. On a quantum computer, this can be done in one step by putting elements in superposition.

F( 0.5|0> + 0.5|9> + 0.5|10> + 0.5|12> ) =

0.5|F(0)> + 0.5|F(9)> + 0.5|F(10)> + 0.5|F(12)> =

0.5|10> + 0.5|0> + 0.5|12> + 0.5|9>

You can see that the input and output states are the same, except for the swap. However, because of the summation, the order doesn't matter. The state has not changed. So the function only permutes the elements. Input and output state can be compared easily. So we can check with a calculation step whether a function only exchanges its elements, or produces new function values.

This algorithm was validated on an IBM-3Qbit-System.

If the function permutes, the measure should return state |000> with 100% certainty. There are other operations that give outputstate |000> as well. But assuming the permuting function is also injective, the probability of alternative ways goes straight against zero. The probability decreases with the number of elements to compare, and exponentially with the number of measurements you do. So, at the end, 10 measures are enough to compare billion elements. Injective permutation could be the scrambled letters in ciphertext: A->H, B->X, C->D, D->U, E->I, F->K, ...

Another application could be, to prove permutations and properties of the monstergroup (group theory), which has almost 10^54 elements.

More details: Algorithm

And: My YouTube-Channel

Answer 1

One problem with this approach is that in quantum state space, permuting the inputs looks a lot like permuting most of the inputs but then doing something that isn't permutation with the remainder of the inputs.

Imagine if your array of inputs were $(0, 1, \dots, 14)$. You load this into the superposition $|\psi\rangle = \frac{1}{\sqrt{15}}\left(|0\rangle + \cdots + |14\rangle \right)$ and then apply either a function $F$ that permutes the inputs (which does nothing to this superposition) or applies a function $F'$ that does not permute the inputs. Suppose $F'$ is the operator that sends $14 \rightarrow 15$ and $15 \rightarrow 14$ and otherwise does nothing to the input. To tell which function was applied, you have to distinguish the two possible states \begin{align} F|\psi\rangle &= \frac{1}{\sqrt{15}}\left(|0\rangle + \cdots + |13\rangle + |14\rangle \right) \\ F'|\psi\rangle &= \frac{1}{\sqrt{15}}\left(|0\rangle + \cdots + |13\rangle + |15\rangle \right) \end{align}

By computing the probability $p_0$ of the all-zeros bitstring, the algorithm you give turns out to be computing $|\langle \psi | S |\psi\rangle|^2$ where $S \in \{F, F'\}$, and your goal is to figure out which function $S$ is. But while you have correctly determined that the probability $p_0$ of measuring all zeros given a permuting function is $$ p_0 = |\langle \psi|F|\psi\rangle|^2 = 1 $$ the probability of measuring all zeros given the non-permuting function $F'$ is \begin{equation} p_0' = |\langle \psi | F' |\psi\rangle|^2 = \frac{14}{15} \end{equation}

That is, when you run the experiment with this choice of non-permuting function, your probability of seeing all zeros is very close to one. In order to convince yourself that you actually had a permuting function and not $F'$ on average you need to run the experiment about 15 times (so that one of the times you see a non-zeros bitstring). But running the experiment 15 times is no faster than the 15 checks you would need to do in the classical case, and so there's not really a good reason to use the quantum computer.