If we want to break someone else's PIN (personal identification number) of, say, an ATM (automated teller machine), how many trials would be necessary when we want to be efficient? This is a sort of what we calla-needle-in-a-hay-stackproblem. In 1987, in their wonderful paper, Hinton & Nowlan proposed a genetic algorithm with a needle being a unique configuration of 20-bit binary string while all other configurations being a haystack. What they proposed was to exploit alifetimelearningof individuals in their genetic algorithm, calling it the Baldwin effectinacomputer. Since then there has been a fair amount of exploration of this effect, claiming, "this is a-needle-in-a-hay-stack problem, and we've found a more efficient algorithm than a random search." Some of them, however, were found to be the results of an effect oflike-to-hear-what-we-would-like-to-hear. In this talk, we will try a bird's eye view on a few examples we have had so far, and how they were explored, including the approach by means of quantum computation which claims, "The steps to find a needle areO(radicN) while those of exhaustive search by a traditional computer are O(N) whereNis the number of search points."
Free tensors are tensors which, after a change of bases, have free support: any two distinct elements of its support differ in at least two coordinates. They play a distinguished role in the theory of bilinear complexity, in particular in Strassen's duality theory for asymptotic rank. Within the context of quantum information theory, where tensors are interpreted as multiparticle quantum states, freeness corresponds to a type of multiparticle Schmidt decomposition. In particular, if a state is free in a given basis, the reduced density matrices are diagonal. Although generic tensors in Cn⊗Cn⊗Cn are non-free for n≥4 by parameter counting, no explicit non-free tensors were known until now. We solve this hay in a haystack problem by constructing explicit tensors that are non-free for every n≥3. In particular, this establishes that non-free tensors exist in Cn⊗Cn⊗Cn, where they are not generic. To establish non-freeness, we use results from geometric invariant theory and the theory of moment polytopes. In particular, we show that if a tensor T is free, then there is a tensor S in the GL-orbit closure of T, whose support is free and whose moment map image is the minimum-norm point of the moment polytope of T. This implies a reduction for checking non-freeness from arbitrary basis changes of T to unitary basis changes of S. The unitary equivariance of the moment map can then be combined with the fact that tensors with free support have diagonal moment map image, in order to further restrict the set of relevant basis changes.
Inspired by a class of algorithms proposed by Farhi et al., namely the quantum approximate optimization algorithm (QAOA), we present a circuit-based quantum algorithm to search for a needle in a haystack, obtaining the same quadratic speedup achieved by Grover's original algorithm. In our algorithm, the problem Hamiltonian (oracle) and a transverse field are applied alternately to the system in a periodic manner. We introduced a novel technique, a spin-coherent-state approach, to analyze the composite unitary in a single period. This composite unitary drives a closed transition between two states that have high degrees of overlap with the initial state and the target state, respectively. The transition rate in our algorithm is of order Θ(1/N), and the overlaps are of order Θ(1), yielding a nearly optimal query complexity of T≃N(π/22). Our algorithm is the first example of a QAOA circuit that demonstrates a quantum advantage with large number of iterations that is not derived from Trotterization of an adiabatic quantum optimization (AQO) algorithm. It also suggests that the analysis required to understand QAOA circuits involves a very different process from estimating the energy gap of a Hamiltonian in AQO.