Find the atom using a quantum oracle

[emmadun]

Homework Statement

I came across a difficult problem that literally blocked my mind and i am not able to solve it in any way. Any help or guidance would be appreciated! Here is the problem:

A newly discovered particle consist of n-atoms and m-bidirectional bonds between them (we are sure the particle is not disconnected). There is exactly one golden atom among the n-atoms and you want to find it with the help of quantum oracle. It allows you to pick a connected set of atoms and tells whether or not the golden atom is among them. You would like to determine a strategy to find the golden atom quickly. You don’t have to ask exactly the minimum possible number of queries. just be efficient.

Relevant Equations

n - atoms

My attempted solutions was, for example let's say we have 4 atoms, and if i ask the oracle about any two atoms that are connected by edge, i can narrow done some possibilities to two atoms.
I'm still not sure where i am going with my solution, but if any of you can think this through and come up with a different strategy or a strategy connecting to mine, i would gladly appreciate it, cause it would help me A LOT.
Thank you! :)

 

[collinsmark]

Is this for a computer science class?

I don't understand the relevance of the bidirectional bonds or why it's important that all particles are connected.

When you say "golden atom" are you speaking specifically about gold (i.e., \rm{\ _{79}Au})? Is this problem for a chemistry class?

 

[emmadun]

Yes, it is in my computer science class.
The bidirectional bonds are relevant so that we now how each atom is connected.
And no, i am not trying to find a LITERAL gold atom, you can think it as any color really, but the point was HOW you can find that "specific" atom (the gold one, in our problem) through a algorithm or come up with a strategy on how you can find it. Various codes can be written, but it is not required. We just need to give an explanation of our strategy on finding it.

 

[collinsmark]

I just want to make sure that the bonds don't matter. Does the golden atom bond differently than the other atoms? In your figure, one of the atoms has three bonds, one at has one bond, and all the other atoms have two bonds. Or does none of that matter?

If the nature of the bonds do not matter, then yes, this problem is relevant for an optimal search algorithm taught in a computer science class.

I have to ask because the problem statement specifically said, "...and m-bidirectional bonds between them." Your attached figure shows both n and m equal to 4. But what if there were 4 atoms (n=4) but there were 5 bonds (m=5)? Why is the number of bonds important enough to mention?

 

[emmadun]

no, it does not bond differently and i think from my perspective, the nature of the bonds are not that relevant, they are stated in the problem so we have an idea of how the atoms are connected i guess. (i mean i wouldn't know for sure but i think i am right)
Basically what is important for us is to find the quickest way to find that specific atom among a bunch of other atoms

 

[collinsmark]

no, it does not bond differently and i think from my perspective, the nature of the bonds are not that relevant, they are stated in the problem so we have an idea of how the atoms are connected i guess. (i mean i wouldn't know for sure but i think i am right)
Basically what is important for us is to find the quickest way to find that specific atom among a bunch of other atoms

Ok then, Let's ignore the bonds and focus on the atoms.

You're on the right track. Can you generalize your algorithm? What if there were 5 atoms? Now what if there were 6 atoms? What about 128 atoms? And finally n atoms?