-2
$\begingroup$

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.

enter image description here

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

$\endgroup$
3
  • 1
    $\begingroup$ Are you assuming it's somehow difficult to test if a value is in the domain of the function, but easy to prepare a superposition over all values in the domain? I otherwise don't see how this could possibly be faster than random testing. It also seems quadratically slower than just using Grover's algorithm to search for escaping inputs. Also, testing a on real QC is more cool than useful... you should be testing using simulators so you can go up to ~30 qubits and actually see query complexity curve. $\endgroup$ Feb 19, 2022 at 20:46
  • $\begingroup$ I just need something plausible to show my colleagues. Let's be honest, Quantumcomputers won't scale. At 1million QBits and more, it gets macroscopic behavior. It becomes exponentially hard to conserve the quantumeffects (coherence) at this large scale. These machines are like an ionocraft. They are working and demonstrated, but no ionocraft/lifter will ever fly passangers over the sea. Sorry for my bad english. Greetings from Germany. $\endgroup$ Feb 20, 2022 at 19:02
  • 1
    $\begingroup$ Welcome to QCSE @MarcoSchmid - I edited your title to sound less unfriendly (you can read more about avoiding unfriendly language in the site code of conduct - quantumcomputing.stackexchange.com/conduct ). Also its usually better to avoid self promotion (such as linking to your personal youtube channel that isn't directly related to the question), otherwise your question might be seen as spam and closed or downvoted- see "How not to be a spammer" quantumcomputing.stackexchange.com/help/promotion. $\endgroup$
    – forky40
    Feb 20, 2022 at 20:25

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I got your point. That's also what I thought first. But for state 1/sqrt(n) (|1> + |2> +... |n> ) you don't need 'n' measurements to distinguish. With some special requirements to the decoder, you can do it with less. And the best argument of all: It's already tested. I fear, the main problem of this algorithm is, what C.Gidney wrote. It's just the complexity to prepare the state. If you have a list with 100 numbers, you need another quantumalgorithm to figure out the gate-arrangement for their superposition. $\endgroup$ Feb 21, 2022 at 18:52