  Remote state preparation (RSP) is the act of preparing a quantum state at a
remote location without actually transmitting the state itself. Using at most
two classical bits and a single shared maximally entangled state, one can in
theory remotely prepare any qubit state with certainty and with perfect
fidelity. However, in any experimental implementation the average fidelity
between the target and output states cannot be perfect. In order for an RSP
experiment to demonstrate genuine quantum advantages, it must surpass the
optimal threshold of a comparable classical protocol. Here we study the
fidelity achievable by RSP protocols lacking shared entanglement, and determine
the optimal value for the average fidelity in several different cases. We
implement an experimental scheme for deterministic remote preparation of
arbitrary photon polarization qubits, preparing 178 different pure and mixed
qubit states with an average fidelity of 0.995. Our experimentally-achieved
average fidelities surpass our derived classical thresholds whenever the
classical protocol does not trivially allow for perfect RSP.
