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

V. Benes, Mathematical Theory of Connecting Networks and Telephone Traffic , ser. Mathematics in science and engineering : a series of monographs and textbooks. Academic Press, 1965. [Online]. Available: https://books.google.co.uk/books?id=nQcjAAAAMAAJ

1965

Earlier work this paper cites.

D. Deutsch, “Quantum computational networks,” Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences , vol. 425, no. 1868, pp. 73–90, 1989. [Online]. Available: http://rspa.royalsocietypublishing.org/content/425/1868/73

1989

Earlier work this paper cites.

J. Dutka, “The early history of the factorial function,” Archive for History of Exact Sciences , vol. 43, no. 3, pp. 225–249, Sep 1991. [Online]. Available: https://doi.org/10.1007/BF00389433

1991

Earlier work this paper cites.

A. C.-C. Yao, “Quantum circuit complexity,” in Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science , Nov 1993, pp. 352–361

1993

Earlier work this paper cites.

R. W. Robinson and N. C. Wormald, “Almost all regular graphs are hamiltonian,” Random Struct. Algorithms , vol. 5, no. 2, pp. 363–374, Apr. 1994. [Online]. Available: http://dx.doi.org/10.1002/rsa.3240050209

1994

Earlier work this paper cites.

A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. A. Smolin, and H. Weinfurter, “Elementary gates for quantum computation,” Phys. Rev. A , vol. 52, pp. 3457–3467, Nov 1995. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.52.3457

1995

Earlier work this paper cites.

B. Bollobas, Random Graphs , 2nd ed., ser. Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2001

2001

Earlier work this paper cites.

A. G. Fowler, S. J. Devitt, and L. C. L. Hollenberg, “Implementation of shor’s algorithm on a linear nearest neighbour qubit array,” eprint arXiv:quant-ph/0402196 , Feb. 2004

2004

Cited alongside, same era.

S. A. Kutin, “Shor’s algorithm on a nearest-neighbor machine,” eprint arXiv:quant-ph/0609001 , Aug. 2006

2006

Cited alongside, same era.

D. Maslov, “Linear depth stabilizer and quantum fourier transformation circuits with no auxiliary qubits in finite-neighbor quantum architectures,” vol. 76, no. 5, p. 052310, Nov. 2007

2007

Cited alongside, same era.

D. Cheung, D. Maslov, and S. Severini, “Translation techniques between quantum circuit architectures,” 2007

2007

Cited alongside, same era.

M. Steffen, D. P. DiVincenzo, J. M. Chow, T. N. Theis, and M. B. Ketchen, “Quantum computing: An IBM perspective,” IBM Journal of Research and Development , vol. 55, no. 5, pp. 13:1–13:11, Sept 2011

R. Beals, S. Brierley, O. Gray, A. W. Harrow, S. Kutin, N. Linden, D. Shepherd, and M. Stather, “Efficient distributed quantum computing,” Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences , vol. 469, no. 2153, 2013. [Online]. Available: http://rspa.royalsocietypublishing.org/content/469/2153/20120686

2013

Later among the works it cites.

N. H. Nickerson, J. F. Fitzsimons, and S. C. Benjamin, “Freely scalable quantum technologies using cells of 5-to-50 qubits with very lossy and noisy photonic links,” Phys. Rev. X , vol. 4, p. 041041, Dec 2014. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevX.4.041041

2014

Later among the works it cites.

R. Nigmatullin, C. J. Ballance, N. de Beaudrap, and S. C. Benjamin, “Minimally complex ion traps as modules for quantum communication and computing,” New Journal of Physics , vol. 18, no. 10, p. 103028, Oct. 2016

2016

Later among the works it cites.