  Randomness is an intrinsic feature of quantum theory. The outcome of any
quantum measurement will be random, sampled from a probability distribution
that is defined by the measured quantum state. The task of sampling from a
prescribed probability distribution is therefore a natural technological
application of quantum devices. In the research presented in this thesis, I
investigate the complexity-theoretic and physical foundations of quantum
sampling algorithms. I assess the computational power of natural quantum
simulators and close loopholes in the complexity-theoretic argument for the
classical intractability of quantum samplers (Part I). I shed light on how and
under which conditions quantum sampling devices can be tested or verified in
regimes that are not simulable on classical computers (Part II). Finally, I
explore the computational boundary between classical and quantum computing
devices (Part III). In particular, I develop efficiently computable measures of
the infamous Monte Carlo sign problem and assess those measures both in terms
of their practicability as a tool for alleviating or easing the sign problem
and the computational complexity of this task.
  An overarching theme of the thesis is the quantum sign problem which arises
due to destructive interference between paths -- an intrinsically quantum
effect. The (non-)existence of a sign problem takes on the role as a criterion
which delineates the boundary between classical and quantum computing devices.
I begin the thesis by identifying the quantum sign problem as a root of the
computational intractability of quantum output probabilities. It turns out that
the intricate structure of the probability distributions the sign problem gives
rise to, prohibits their verification from few samples. In an ironic twist, I
show that assessing the intrinsic sign problem of a quantum system is again an
intractable problem.
