  How long does it take to entangle two distant qubits in a quantum circuit
evolved by generic unitary dynamics? We show that if the time evolution is
followed by measurements of all but two infinitely separated test qubits, then
the entanglement between them can undergo a phase transition and become nonzero
at a finite critical time $t_c$. The fidelity of teleporting a quantum state
from an input qubit to an infinitely distant output qubit shows the same
critical onset. Specifically, these finite-time transitions occur in
short-range interacting two-dimensional random unitary circuits and in
sufficiently long-range interacting one-dimensional circuits. The phase
transition is understood by mapping the random continuous-time evolution to a
finite-temperature thermal state of an effective spin Hamiltonian, where the
inverse temperature equals the evolution time in the circuit. In this
framework, the entanglement between two distant qubits at times $t>t_c$
corresponds to the emergence of long-range ferromagnetic spin correlations
below the critical temperature. We verify these predictions using numerical
simulation of Clifford circuits and propose potential realizations in existing
platforms for quantum simulation.
