Search Talks

Complexity class MA is a class of yes/no problems for which the answer `yes\' has a short certificate that can be efficiently checked by a classical randomized algorithm. We prove that MA has a natural complete problem: stoquastic k-SAT. This is a quantum-mechanical analogue of the satisfiability problem such that k-bit clauses are replaced by k-qubit projectors with non-negative matrix elements. Complexity class AM is a generalization of MA in which the certificate may include a short conversation between Prover and Verifier. We prove that AM also has a natural complete problem: stoquastic Local Hamiltonian with a quenched disorder. The problem is to evaluate expectation value of the ground state energy of disordered local Hamiltonian with non-positive matrix elements.

The nature of an unusual class of cosmic X-ray source, dubbed "Anomalous X-ray Pulsars," was a mystery since 1982 when the first example was discovered. In this talk, I will show the recent observational evidence that unambiguously links them with another equally exotic class of object, the explosive "Soft Gamma Repeaters." The evidence todate strongly supports the picture that both are "magnetars:" isolated young neutron stars having surface magnetic fields ~1000 times greater than those in conventional neutron stars.