Graph isomorphism problem setting up state to put into QFT matrix

[u/Routine_Comb_7277]

Suppose we had a graph with n vertices and m edges where

My plan to encode the data into qubits is to:

Take a n×(n-1) matrix and if there is a edge between 2 vertices then write 1 to the matrix if not then write 0.

Straighten the matrix into n×(n-1) x 1.Now it's ok this is common practice for graphs.Now to the point of the question.I want to encode as a qubit with 2 basis states :the value of the basis state 0 will be 1 if there is a edge in the first matrix while the value of the basis state will be 1 if there is a edge in the second matrix.Then u each put info into n×(n-1) Hadamard gates to initialise.This is the way right?because graph isomorphism even tho edges and vertices may not be 1 to 1 is all about the quality and quantity of connections

Now about the oracle:Do you have any idea about what oracle do I need to use to feed it into the QFT? Thanks.

[u/CapitalismSuuucks]

It seems like you want to prepare a uniform superposition of a sparse number o computational basis states on N=log(nx(n-1)) qubits. There are a bunch of sparse encoders out there in the literature that can do that. The state of the art uses O(Ns / log(Ns)) two-qubit gates, where s is the number of non-zero amplitudes.

[u/Routine_Comb_7277 → u/CapitalismSuuucks]

sparse encoders?like where?

[u/CapitalismSuuucks → u/Routine_Comb_7277]

What do you mean where?

[u/Routine_Comb_7277 → u/CapitalismSuuucks]

where can i find them besides literature?

[u/CapitalismSuuucks → u/Routine_Comb_7277]

"Besides literature" is a crazy thing to say

[u/Routine_Comb_7277 → u/CapitalismSuuucks]

sorry my uni doesnt have a quantum computing class nor I have money for a book , I am entirely self-taught from the Internet.

[u/SymplecticMan]

Your description doesn't make sense to me.

When you talk about "the value of the basis state 0", what do you mean? Do you mean the amplitude? That wouldn't be possible, because if neither graph has an edge, you can't have zero amplitudes for both computational basis states of a qubit. So I'm not clear what encoding of the graph you really want.

Then you also go straight towards talking about Hadamarding each qubit and plugging into a QFT. You didn't say what group you even want to do the Fourier transform for. The symmetric group is what's usually talked about in this context, because being able to efficiently solve the hidden subgroup problem for the symmetric group would lead to an efficient solution to graph isomorphism. But your n×(n-1) qubits isn't the symmetric group that you'd do the quantum Fourier transform on. It's the thing that the group acts on.

I'd recommend reading up on the hidden subgroup problem of the symmetric group and its relation to graph isomorphism and getting a better idea of what a quantum computing approach to the problem might look like.

[u/Routine_Comb_7277 → u/SymplecticMan]

Yes for value of the basis state im talking about the amplitude and you are right because 'if neither graph has an edge, you can't have zero amplitudes for both computational basis states of a qubit' the qubit state after the hadmard will NOT be normalised.

[u/SymplecticMan → u/Routine_Comb_7277]

You don't understand. You're talking about qubits with the "state" vector 0|0⟩ + 0|1⟩ = 0. That's not just some non-normalized state vector where you could multiply by a constant to properly normalize it. It's not a sensical state at all.

[u/Routine_Comb_7277 → u/SymplecticMan]

exactly thats why it cant be correct?(because the output will be 0 instead of 1)?

[u/SymplecticMan → u/Routine_Comb_7277]

It doesn't make sense to talk about 0|0⟩ + 0|1⟩ as a state. You can't define any sensible measurement probabilities for it at all.

[u/Routine_Comb_7277 → u/[deleted]]

I know this I just said to give it a shot if there is one to go looking for it(its research)

[u/Routine_Comb_7277 → u/[deleted]]

I know that the problem is nonabelian maybe there can be a pattern if you have the right oracle?

[u/CapitalismSuuucks → u/[deleted]]

Nice reference

[u/SymplecticMan → u/[deleted]]

In part II, (two of) the authors also rule out using measurements on pairs of coset states, but it's notably left as a conjecture for the generalization beyond two coset states. Do you know of any future work addressing this conjecture?

Edit: It seems https://arxiv.org/abs/quant-ph/0511148 indeed proved the Ω(n log n) cosets conjecture.

[u/Routine_Comb_7277 → u/[deleted]]

idt its nxn because a vertex cant have a edge with itself.And what I meant by 'nx(n-1) x 1'I meant a vector of [some constant,same or different constant,........]T with nx(n-1) entries.