Polylogarithmic-depth controlled-NOT gates without ancilla qubits.

Controlled operations are fundamental building blocks of quantum algorithms. Decomposing n-control-NOT gates (Cn(X)) into arbitrary single-qubit and CNOT gates, is a crucial but non-trivial task. This study introduces Cn(X) circuits outperforming previous methods in the asymptotic and non-asymptotic regimes. Three distinct decompositions are presented: an exact one using one borrowed ancilla with a circuit depth Θ ( log ( n ) 3 ) , an approximating one without ancilla qubits with a circuit depth O ( log ( n ) 3 log ( 1 / ϵ ) ) and an exact one with an adjustable-depth circuit which decreases with the number m≤n of ancilla qubits available as O ( log ( n / ⌊ m / 2 ⌋ ) 3 + log ( ⌊ m / 2 ⌋ ) ) . The resulting exponential speedup is likely to have a substantial impact on fault-tolerant quantum computing by improving the complexities of countless quantum algorithms with applications ranging from quantum chemistry to physics, finance and quantum machine learning.

Programmable high-dimensional Hamiltonian in a photonic waveguide array.

Waveguide lattices offer a compact and stable platform for a range of applications, including quantum walks, condensed matter system simulation, and classical and quantum information processing. However, to date, waveguide lattice devices have been static and designed for specific applications. We present a programmable waveguide array in which the Hamiltonian terms can be individually electro-optically tuned to implement various Hamiltonian continuous-time evolutions on a single device. We used a single array with 11 waveguides in lithium niobate, controlled via 22 electrodes, to perform a range of experiments that realized the Su-Schriffer-Heeger model, the Aubrey-Andre model, and Anderson localization, which is equivalent to over 2500 static devices. Our architecture's micron-scale local electric fields overcome the cross-talk limitations of thermo-optic phase shifters in other platforms such as silicon, silicon-nitride, and silica. Electro-optic control allows for ultra-fast and more precise reconfigurability with lower power consumption, and with quantum input states, our platform can enable the study of multiple condensed matter quantum dynamics with a single device.