Lower bounds on the complexity of simulating quantum gates

2003/07/25 by Andrew M. Childs, Henry L. Haselgrove, Michael A. Nielsen
Computer Science · Physics and Astronomy · #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Mechanics and Applications #quant-ph

paper · pdf · doi:10.1103/physreva.68.052311

published as Phys. Rev. A 68, 052311 (2003) · 6 pages

arxiv created 2003/07/25 · openalex publication_date 2003/11/18 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We give a simple proof of a formula for the minimal time required to simulate a two-qubit unitary operation using a fixed two-qubit Hamiltonian together with fast local unitaries. We also note that a related lower bound holds for arbitrary n-qubit gates.

Citations

• Nonlocal Properties of Two-Qubit Gates and Mixed States, and the Optimization of Quantum Computations
• Universal simulation of Hamiltonian dynamics for quantum systems with finite-dimensional state spaces
• Entanglement of a Pair of Quantum Bits

Related

• Explicit lower bounds on strong simulation of quantum circuits in terms of T-gate count
• Explicit lower bounds on strong quantum simulation
• Quantum Computing with Global One-and Two-Qubit Gates
• Local Hamiltonian decomposition and classical simulation of parametrized quantum circuits
• Optimal Lower Bounds for Hamiltonian Simulation