  Suppose we are given an oracle that claims to approximate the permanent for
most matrices X, where X is chosen from the Gaussian ensemble (the matrix
entries are i.i.d. univariate complex Gaussians). Can we test that the oracle
satisfies this claim? This paper gives a polynomial-time algorithm for the
task. The oracle-testing problem is of interest because a recent paper of
Aaronson and Arkhipov showed that if there is a polynomial-time algorithm for
simulating boson-boson interactions in quantum mechanics, then an approximation
oracle for the permanent (of the type described above) exists in BPP^NP. Since
computing the permanent of even 0/1 matrices is #P-complete, this seems to
demonstrate more computational power in quantum mechanics than Shor's factoring
algorithm does. However, unlike factoring, which is in NP, it was unclear
previously how to test the correctness of an approximation oracle for the
permanent, and this is the contribution of the paper. The technical difficulty
overcome here is that univariate polynomial self-correction, which underlies
similar oracle-testing algorithms for permanent over finite fields --- and
whose discovery led to a revolution in complexity theory --- does not seem to
generalize to complex (or even, real) numbers. We believe that this tester will
motivate further progress on understanding the permanent of Gaussian matrices.
