Loss Function

How to statistically prove that the DWave "minimal energy" (and the results inferred) are close to the expected optimal value?

e.g.: if I know that the "optimal value" is "0.01" and DWave found "0.1", this value is 10x bigger than the expected value (this is bad); but if the Worst value (max energy) is 1000 so DWave found a solution much more closely to the optimal value than just random guesses.

Is there some "Loss Function" (or anything statistically related) to differentiate the quality of the DWave quantum optimization results, from simple random sampling results that by a chance can find a small value.

Thank you

0

Comments

3 comments
  • Hello,

    Just to paraphrase what you are saying is something like "How good is the answer if it isn't ground state?", is this correct?

    We could approach this by saying that the difficulty of approximating the ground state with a fractional error of 1-epsilon scales as 2^32/epsilon for Chimera graphs.

    See this paper:
    https://arxiv.org/pdf/1306.6943.pdf

    This does not provide a very tight bound, and doesn't pose a big challenge for D-Wave or any other heuristic solver.
    Basically it just illustrates the notion that answers close to ground state are harder to find that answers further from ground state.

    We expect an energy of zero for random sampling of any Ising model.

    More accurate approximations will depend on the system or problem being studied.

    I hope this helps to answer your quesiton.

    Please feel free to reach out with more questions.

    0
    Comment actions Permalink
  • Thank you so much, but I think that paper is concerned with a polynomial-Time approximation.

    In two situations, 1) knowing the minimal value and 2) don't know the minimal value.

    How can I prove that all the DWave Energies (not only the minimal energy) are a good attempt to find the global minimum value and isn't just several random guesses that by a coincidence found a small value?

    Basically, how can trust in the quality of the response energies?

    Thank you.

    0
    Comment actions Permalink
  • Hi Cid,

    If you are formulating your energy function in Ising form (-1,1) rather than QUBO form (0,0), it is always the case that the average energy of a random sample is zero.

    If you look at the average energy of an output sample (from D-Wave or something else) and divide that sample by the sum of absolute values of h and J terms, you should generally get a number that is significantly less than zero and significantly more than -1 (assuming the problem is hard).

    The easiest thing to do here is take the D-Wave output energies, take the energies of a bunch of random samples, and compare them.  As I said, normalizing by the sum of magnitudes of nonzero Hamiltonian terms (h's and J's) will give you a number that is in some way agnostic to the input.

    Hope this helps,

    Andrew

    0
    Comment actions Permalink

Please sign in to leave a comment.

Didn't find what you were looking for?

New post