On the depth overhead incurred when running quantum algorithms on near-term quantum computers with limited qubit connectivity

This paper proves that some there are some quantum circuits that will always incur a logarithmic depth overhead when executed on a real machine. It is also shown that this logarithmic depth overhead is always achievable when the quantum computer has an interaction graph that is only constrained to be r-regular for some specified r: proving this is the case for any r > 3, and conjecturing that it will still be true when r=3.

Steven J. Herbert

Post by admin