1. Sounds like you should be able to describe this algorythm without mentioning anything quantum at all, just you know, sets of complex numbers calculated in a certain way. It might be a good idea to do just that - precisely formulate it without referencing quantum stuff.

2. "If an equal fingerprint was found, graphs are isomorphic, otherwise not." - I expect this step to fail. Either there will be isomorphic graphs will different fingerprints, or different graphs with same fingerprints. You'll have to specify your "wave" process exactly and then make an honest attempt to break it with a counterexample.

@Tasty_Y I think it would "work", but it would require exponential runtime, since there are exponentially many fingerprints.

@CharlesLien there are n^2 fingerprints, for each pair of source-sink vertices.

@AnT well if that's how you're classifying fingerprints, the comparison of two fingerprints would take exponential time.

@CharlesLien why? You could just impose some ordering on them and then compare one by one. Same as comparing any two lists for equality.

@jonsimon Comparing lists is a different problem. For lists, you know the ordering of each of the elements. Is the list [1, 2] the same as [2, 1]? The answer should be yes, because those two graphs would be isomorphic.

But then your algorithm no longer works. Checking element by element gives that the lists are not indeed equal.

If your response is "just sort the lists first", you need to come up with an ordering of the nodes that is the same for the same graphs. And at that point, you're just solving the graph isomorphism problem.

So this is just converting the graph isomorphism problem to the graph isomorphism problem where you know two nodes must correspond.

@CharlesLien OP's idea is that you'd get two... not sets exactly, but two piles of numbers like say (1, 1, 1, 2, 2) and (2, 2, 1, 1, 1) and if they have the same contents, like in this case, the graphs would be isomorphic. You can verify that two piles have the same contents in quadratic time (grab any element of the first pile, search for it in the second pile, either find it and remove it from both piles and continue or not find it and end the process), but I expect it simply won't be the case that piles will have the same contents iff the graphs are isomorphic.

@CharlesLien And I'm saying to sort the lists before comparing them. That makes it linear. You can sort complex numbers just fine.

Quantum computers aren't the same thing as a non-deterministic turing machine. just because something could be computed with infinite parallelization doesn't mean you can easily compute it on a quantum computer.

There are very specific algorithms that it HAPPENS to work for.

Subgraph isomorphism is NP-complete. If this algorithm works and the fingerprint function is any recursive or linear function, there's probably a way to invert a matrix or binary search to find the subgraph that is isomorphic.

Also look at the Reconstruction Conjecture: Trying to infer something about the whole graph by looking at vertex-deleted subgraphs is going to be hard, and step #3 depending on how you implement it might be phrased in terms of vertex-deleted subgraphs.

What about this is quantum? What do you mean by 'create wave'?

@AdamTreat

1. Why I think this is related to quantum computers is that they are more capable of parallel information processing;

2. Create wave... I imagine that as "each node has certain complex number and they are changing according to numbers in neighbor nodes like in dynamic system".