2025/04/12 by Franz Fuchs, Fuchs, Franz G., Ruben Pariente Bassa +1
Computer Science · Physics and Astronomy · #Complexity and Algorithms in Graphs #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #Quantum many-body systems
paper · pdf · doi:10.48550/arxiv.2504.09133
openalex publication_date 2025/04/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We introduce a general framework for constructing compact quantum circuits that implement the real-time evolution of Hamiltonians of the form H = σPB, where σ is a Pauli string commuting with a projection operator PB onto a subspace of the computational basis. Such Hamiltonians frequently arise in quantum algorithms, including constrained mixers in QAOA, fermionic and excitation operators in VQE, and lattice gauge theory applications. Additionally, we construct transposition gates, widely used in quantum computing, that scale more efficiently than the best known constructions in literature. Our method emphasizes the minimization of non-transversal gates, particularly T-gates, critical for fault-tolerant quantum computing. We construct circuits requiring O(n|B|) CX gates and O(n |B| + log(|B|) log (1/ε)) T-gates, where n is the number of qubits, |B| the dimension of the projected subspace, and ε the desired approximation precision. For subspaces that are generated by Pauli X-orbits we further reduce complexity to O(n log |B|) CX gates and O(n+log(\frac1ε)) T gates. Our constructive proofs yield explicit algorithms and include several applications, such as improved transposition circuits, efficient implementations of fermionic excitations, and oracle operators for combinatorial optimization. In the sparse case, i.e. when |B| is small, the proposed algorithms scale favourably when compared to direct Pauli evolution.