  Secure multi-party computing, also called "secure function evaluation", has
been extensively studied in classical cryptography. We consider the extension
of this task to computation with quantum inputs and circuits. Our protocols are
information-theoretically secure, i.e. no assumptions are made on the
computational power of the adversary. For the weaker task of verifiable quantum
secret sharing, we give a protocol which tolerates any t < n/4 cheating parties
(out of n). This is shown to be optimal. We use this new tool to show how to
perform any multi-party quantum computation as long as the number of dishonest
players is less than n/6.
