2018/05/31 by Steven Herbert, Herbert, Steven · 3 citations
Computer Science · Engineering · #FOS: Physical sciences #Low-power high-performance VLSI design #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #Quantum-Dot Cellular Automata
paper · pdf · doi:10.48550/arxiv.1805.12570
openalex publication_date 2018/05/31 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28
This paper addresses the problem of finding the depth overhead that will be\nincurred when running quantum circuits on near-term quantum computers.\nSpecifically, it is envisaged that near-term quantum computers will have low\nqubit connectivity: each qubit will only be able to interact with a subset of\nthe other qubits, a reality typically represented by a qubit interaction graph\nin which a vertex represents a qubit and an edge represents a possible direct\n2-qubit interaction (gate). Thus the depth overhead is unavoidably incurred by\nintroducing swap gates into the quantum circuit to enable general qubit\ninteractions. This paper proves that there exist quantum circuits where a depth\noverhead in \Ω(\log n) must necessarily be incurred when running quantum\ncircuits with n qubits on quantum computers whose qubit interaction graph has\nfinite degree, but that such a logarithmic depth overhead is achievable. The\nlatter is shown by the construction of a 4-regular qubit interaction graph and\nassociated compilation algorithm that can execute any quantum circuit with only\na logarithmic depth overhead.\n