Speaker:
Institution:
Time:
Location:
Let a_ij be a finite collection of real numbers, and let s_i and s_j be spins (they take only two values +1 or -1). The goal is to choose the spins s_i and s_j so that to maximize the double sum a_ij s_i s_j, where the summation runs over all indecies from 1 to n such that i does not qual to j. If a_ij =1 then the sum is maximized if all spins have the same sign which gives the result to be of order n^2. However, if a_ij=-1 then the sum is maximized when half of the spins take value 1 and the other half -1. When a_ij are arbitrary real numbers this becomes a nontrivial problem (also known as Dean's problem). The problem is well understood in average when a_ij are i.i.d symmetric +1 or -1 random vairables (the Sherrington--Kirkpatrick model). We will speak about possible lower bounds of the maximum in terms of arbitrary real numbers a_ij, its extensions to d-spin case, some conjectures in this area, and their applications in quantum computing.