Efficiently entangling pairs of qubits is essential to fully harness the power of quantum computing. Here, we devise an exact protocol that simultaneously entangles arbitrary pairs of qubits on a trapped-ion quantum computer. The protocol requires classical computational resources polynomial in the system size, and very little overhead in the quantum control compared to a single-pair case. We demonstrate an exponential improvement in both classical and quantum resources over the current state of the art. We implement the protocol on a software-defined trapped-ion quantum computer, where we reconfigure the quantum computer architecture on demand. Together with the all-to-all connectivity available in trapped-ion quantum computers, our results establish that trapped ions are a prime candidate for a scalable quantum computing platform with minimal quantum latency.