  A test of quantumness is a protocol that allows a classical verifier to
certify (only) that a prover is not classical. We show that tests of
quantumness that follow a certain template, which captures recent proposals
such as (Kalai et al., 2022), can in fact do much more. Namely, the same
protocols can be used for certifying a qubit, a building-block that stands at
the heart of applications such as certifiable randomness and classical
delegation of quantum computation.
  Certifying qubits was previously only known to be possible based on the
hardness of the Learning with Errors problem and the use of adaptive hardcore
(Brakerski et al., 2018). Our framework allows certification of qubits based
only on the existence of post-quantum trapdoor claw-free functions, or on
quantum fully homomorphic encryption. These can be instantiated, for example,
from Ring Learning with Errors.
  On the technical side, we show that the quantum soundness of any such
protocol can be reduced to proving a bound on a simple algorithmic task:
informally, answering ``two challenges simultaneously'' in the protocol. Our
reduction formalizes the intuition that these protocols demonstrate quantumness
by leveraging the impossibility of rewinding a general quantum prover. This
allows us to prove tight bounds on the quantum soundness of (Kahanamoku-Meyer
et al., 2021) and (Kalai et al., 2022), showing that no quantum polynomial-time
prover can succeed with probability larger than $\cos^2 \frac{\pi}{8}\approx
0.853$. Previously, only an upper bound on the success probability of classical
provers, and a lower bound on the success probability of quantum provers, were
known. We then extend this proof of quantum soundness to show that provers that
approach the quantum soundness bound must perform almost anti-commuting
measurements. This certifies that the prover holds a qubit.
