  In this paper we consider a quantum computational variant of nondeterminism
based on the notion of a quantum proof, which is a quantum state that plays a
role similar to a certificate in an NP-type proof. Specifically, we consider
quantum proofs for properties of black-box groups, which are finite groups
whose elements are encoded as strings of a given length and whose group
operations are performed by a group oracle. We prove that for an arbitrary
group oracle there exist succinct (polynomial-length) quantum proofs for the
Group Non-Membership problem that can be checked with small error in polynomial
time on a quantum computer. Classically this is impossible--it is proved that
there exists a group oracle relative to which this problem does not have
succinct proofs that can be checked classically with bounded error in
polynomial time (i.e., the problem is not in MA relative to the group oracle
constructed). By considering a certain subproblem of the Group Non-Membership
problem we obtain a simple proof that there exists an oracle relative to which
BQP is not contained in MA. Finally, we show that quantum proofs for
non-membership and classical proofs for various other group properties can be
combined to yield succinct quantum proofs for other group properties not having
succinct proofs in the classical setting, such as verifying that a number
divides the order of a group and verifying that a group is not a simple group.
