  Secret sharing and multiparty computation (also called "secure function
evaluation") are fundamental primitives in modern cryptography, allowing a
group of mutually distrustful players to perform correct, distributed
computations under the sole assumption that some number of them will follow the
protocol honestly. This paper investigates how much trust is necessary -- that
is, how many players must remain honest -- in order for distributed quantum
computations to be possible.
  We present a verifiable quantum secret sharing (VQSS) protocol, and a general
secure multiparty quantum computation (MPQC) protocol, which can tolerate any
(n-1)/2 (rounded down) cheaters among n players. Previous protocols for these
tasks tolerated (n-1)/4 (rounded down) and (n-1)/6 (rounded down) cheaters,
respectively. The threshold we achieve is tight - even in the classical case,
``fair'' multiparty computation is not possible if any set of n/2 players can
cheat.
  Our protocols rely on approximate quantum error-correcting codes, which can
tolerate a larger fraction of errors than traditional, exact codes. We
introduce new families of authentication schemes and approximate codes tailored
to the needs of our protocols, as well as new state purification techniques
along the lines of those used in fault-tolerant quantum circuits.
