  We propose a universal gate set for quantum computing with all-to-all
connectivity and intrinsic robustness to bit-flip errors based on parity
encoding. We show that logical controlled phase gate and $R_z$ rotations can be
implemented in parity encoding with single-qubit operations. Together with
logical $R_x$ rotations, implemented via nearest-neighbor controlled-NOT gates
and an $R_x$ rotation, these form a universal gate set. As the controlled phase
gate requires only single-qubit rotations, the proposed scheme has advantages
for several cornerstone quantum algorithms, e.g., the quantum Fourier
transform. We present a method to switch between different encoding variants
via partial on-the-fly encoding and decoding.
