Built on

K. Smith, M. Thornton, M. Soeken, B. Schmitt, and G. de Micheli, Electronic Proceedings in Theoretical Computer Science, EPTCS 318
Original
1901
Earlier work this paper cites.
P. Murali, J. M. Baker, A. J. Abhari, F. T. Chong, and M. Martonosi, International Conference on Architectural Support for Programming Languages and Operating Systems - ASPLOS , 1015 (2019) , arXiv:1901.11054
Original
1901
Earlier work this paper cites.
R. Wille, L. Burgholzer, and A. Zulehner, in Proceedings - Design Automation Conference (2019) arXiv:1907.02026
Original
1907
Earlier work this paper cites.
X. Zhou, S. Li, and Y. Feng, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems , 1 (2020) , 1908.08853
Original
1908
Earlier work this paper cites.
J. X. Lin, E. R. Anschuetz, and A. W. Harrow, “Using spectral graph theory to map qubits onto connectivity-limited devices,” (2019), arXiv:1910.11489 [quant-ph]
Original
1910
Earlier work this paper cites.
D. Bhattacharjee, A. A. Saki, M. Alam, A. Chattopadhyay, and S. Ghosh, “Muqut: Multi-constraint quantum circuit mapping on noisy intermediate-scale quantum computers,” (2019), arXiv:1911.08559 [quant-ph]
Original
1911
Earlier work this paper cites.
B. Lodewijks, “Mapping np-hard and np-complete optimisation problems to quadratic unconstrained binary optimisation problems,” (2019), arXiv:1911.08043 [cs.DS]
Original
1911
Earlier work this paper cites.
H. Deng, Y. Zhang, and Q. Li, “Codar: A contextual duration-aware qubit mapping for various nisq devices,” (2020), arXiv:2002.10915 [quant-ph]
Original
2002
Earlier work this paper cites.
C. Zhang, Y. Chen, Y. Jin, W. Ahn, Y. Zhang, and E. Z. Zhang, “A depth-aware swap insertion scheme for the qubit mapping problem,” (2020), arXiv:2002.07289 [cs.ET]
Original
2002
Earlier work this paper cites.
M. Webber, S. Herbert, S. Weidt, and W. K. Hensinger, “Efficient qubit routing for a globally connected trapped ion quantum computer,” (2020), arXiv:2002.12782 [quant-ph]
Original
2002
Earlier work this paper cites.
S. Li, X. Zhou, and Y. Feng, “Qubit mapping based on subgraph isomorphism and filtered depth-limited search,” (2020), arXiv:2004.07138 [quant-ph]
Original
2004
Earlier work this paper cites.
E. Wilson, S. Singh, and F. Mueller, “Just-in-time quantum circuit transpilation reduces noise,” (2020), arXiv:2005.12820 [quant-ph]
Original
2005
Earlier work this paper cites.
B. Tan and J. Cong, “Optimal layout synthesis for quantum computing,” (2020a), arXiv:2007.15671 [cs.AR]
Original
2007
Earlier work this paper cites.
A. Paler, L. M. Sasu, A. Florea, and R. Andonie, “Machine learning optimization of quantum circuit layouts,” (2020), arXiv:2007.14608 [quant-ph]
Original
2007
Earlier work this paper cites.

Similar

M. G. Pozzi, S. J. Herbert, A. Sengupta, and R. D. Mullins, “Using reinforcement learning to perform qubit routing in quantum compilers,” (2020), arXiv:2007.15957 [quant-ph]
Original
2007
Cited alongside, same era.
P. Jurcevic et al., “Demonstration of quantum volume 64 on a superconducting quantum computing system,” (2020), arXiv:2008.08571 [quant-ph]
Original
2008
Cited alongside, same era.
R. E. Burkard, in Handbook of Combinatorial Optimization , Vol. 5-5 (Springer New York, 2013) pp. 2741–2814
2013
Cited alongside, same era.
G. Kochenberger, J. K. Hao, F. Glover, M. Lewis, Z. Lü, H. Wang, and Y. Wang, Journal of Combinatorial Optimization 28
2014
Cited alongside, same era.
A. Lucas, Frontiers in Physics 2
2014
Cited alongside, same era.

Then

A. M. Childs, E. Schoute, and C. M. Unsal, Proceedings of TQC 2019, LIPIcs 135
2019
Later among the works it cites.
A. Zulehner and R. Wille, in Proceedings of the 24th Asia and South Pacific Design Automation Conference , ASPDAC ’19 (Association for Computing Machinery, New York, NY, USA, 2019) p. 185–190
2019
Later among the works it cites.
A. Paler, in Quantum Technology and Optimization Problems , edited by S. y. Feld and C. Linnhoff-Popien (Springer International Publishing, Cham, 2019) pp. 207–217, 1811.08985
Original
2019
Later among the works it cites.
H. A. et al., “Qiskit: An open-source framework for quantum computing,” (2019)
2019
Later among the works it cites.
Google, “ Cirq
2019
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…

2020

A QUBO Formulation for Qubit Allocation

Dury, Bryan, Di Matteo, Olivia

Understand

To run an algorithm on a quantum computer, one must choose an assignment from logical qubits in a circuit to physical qubits on quantum hardware.

This task of initial qubit placement, or qubit allocation, is especially important on present-day quantum computers which have a limited number of qubits, connectivity constraints, and varying gate fidelities.
In this work we formulate and implement the qubit placement problem as a quadratic, unconstrained binary optimization (QUBO) problem and solve it using simulated annealing to obtain a spectrum of initial placements.
Compared to contemporary allocation methods available in t|ket$\rangle $ and Qiskit, the QUBO method yields allocations with improved circuit depth for $>$50% of a large set of benchmark circuits, with many also requiring fewer CX gates.

Built on

K. Smith, M. Thornton, M. Soeken, B. Schmitt, and G. de Micheli, Electronic Proceedings in Theoretical Computer Science, EPTCS 318
Original
1901
Earlier work this paper cites.
P. Murali, J. M. Baker, A. J. Abhari, F. T. Chong, and M. Martonosi, International Conference on Architectural Support for Programming Languages and Operating Systems - ASPLOS , 1015 (2019) , arXiv:1901.11054
Original
1901
Earlier work this paper cites.
R. Wille, L. Burgholzer, and A. Zulehner, in Proceedings - Design Automation Conference (2019) arXiv:1907.02026
Original
1907
Earlier work this paper cites.
X. Zhou, S. Li, and Y. Feng, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems , 1 (2020) , 1908.08853
Original
1908
Earlier work this paper cites.
J. X. Lin, E. R. Anschuetz, and A. W. Harrow, “Using spectral graph theory to map qubits onto connectivity-limited devices,” (2019), arXiv:1910.11489 [quant-ph]
Original
1910
Earlier work this paper cites.
D. Bhattacharjee, A. A. Saki, M. Alam, A. Chattopadhyay, and S. Ghosh, “Muqut: Multi-constraint quantum circuit mapping on noisy intermediate-scale quantum computers,” (2019), arXiv:1911.08559 [quant-ph]
Original
1911
Earlier work this paper cites.
B. Lodewijks, “Mapping np-hard and np-complete optimisation problems to quadratic unconstrained binary optimisation problems,” (2019), arXiv:1911.08043 [cs.DS]
Original
1911
Earlier work this paper cites.
H. Deng, Y. Zhang, and Q. Li, “Codar: A contextual duration-aware qubit mapping for various nisq devices,” (2020), arXiv:2002.10915 [quant-ph]
Original
2002
Earlier work this paper cites.
C. Zhang, Y. Chen, Y. Jin, W. Ahn, Y. Zhang, and E. Z. Zhang, “A depth-aware swap insertion scheme for the qubit mapping problem,” (2020), arXiv:2002.07289 [cs.ET]
Original
2002
Earlier work this paper cites.
M. Webber, S. Herbert, S. Weidt, and W. K. Hensinger, “Efficient qubit routing for a globally connected trapped ion quantum computer,” (2020), arXiv:2002.12782 [quant-ph]
Original
2002
Earlier work this paper cites.
S. Li, X. Zhou, and Y. Feng, “Qubit mapping based on subgraph isomorphism and filtered depth-limited search,” (2020), arXiv:2004.07138 [quant-ph]
Original
2004
Earlier work this paper cites.
E. Wilson, S. Singh, and F. Mueller, “Just-in-time quantum circuit transpilation reduces noise,” (2020), arXiv:2005.12820 [quant-ph]
Original
2005
Earlier work this paper cites.
B. Tan and J. Cong, “Optimal layout synthesis for quantum computing,” (2020a), arXiv:2007.15671 [cs.AR]
Original
2007
Earlier work this paper cites.
A. Paler, L. M. Sasu, A. Florea, and R. Andonie, “Machine learning optimization of quantum circuit layouts,” (2020), arXiv:2007.14608 [quant-ph]
Original
2007
Earlier work this paper cites.

Similar

M. G. Pozzi, S. J. Herbert, A. Sengupta, and R. D. Mullins, “Using reinforcement learning to perform qubit routing in quantum compilers,” (2020), arXiv:2007.15957 [quant-ph]
Original
2007
Cited alongside, same era.
P. Jurcevic et al., “Demonstration of quantum volume 64 on a superconducting quantum computing system,” (2020), arXiv:2008.08571 [quant-ph]
Original
2008
Cited alongside, same era.
R. E. Burkard, in Handbook of Combinatorial Optimization , Vol. 5-5 (Springer New York, 2013) pp. 2741–2814
2013
Cited alongside, same era.
G. Kochenberger, J. K. Hao, F. Glover, M. Lewis, Z. Lü, H. Wang, and Y. Wang, Journal of Combinatorial Optimization 28
2014
Cited alongside, same era.
A. Lucas, Frontiers in Physics 2
2014
Cited alongside, same era.

Then

A. M. Childs, E. Schoute, and C. M. Unsal, Proceedings of TQC 2019, LIPIcs 135
2019
Later among the works it cites.
A. Zulehner and R. Wille, in Proceedings of the 24th Asia and South Pacific Design Automation Conference , ASPDAC ’19 (Association for Computing Machinery, New York, NY, USA, 2019) p. 185–190
2019
Later among the works it cites.
A. Paler, in Quantum Technology and Optimization Problems , edited by S. y. Feld and C. Linnhoff-Popien (Springer International Publishing, Cham, 2019) pp. 207–217, 1811.08985
Original
2019
Later among the works it cites.
H. A. et al., “Qiskit: An open-source framework for quantum computing,” (2019)
2019
Later among the works it cites.
Google, “ Cirq
2019
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

S. Brierley, “Efficient implementation of quantum circuits with limited qubit interactions,” (2015), arXiv:1507.04263 [quant-ph]

Original

2015

Cited alongside, same era.

M. Pedram and A. Shafaei, IEEE Circuits and Systems Magazine 16

2016

Cited alongside, same era.

M. Y. Siraichi, V. F. d. Santos, S. Collange, and F. M. Q. Pereira, in Proceedings of the 2018 International Symposium on Code Generation and Optimization , CGO 2018 (Association for Computing Machinery, New York, NY, USA, 2018) p. 113–125

2018

Cited alongside, same era.

G. W. Dueck, A. Pathak, M. M. Rahman, A. Shukla, and A. Banerjee, in 2018 21st Euromicro Conference on Digital System Design (DSD) (2018) pp. 680–684

2018

Cited alongside, same era.

S. Herbert and A. Sengupta, “Using reinforcement learning to find efficient qubit routing policies for deployment in near-term quantum computers,” (2018), arXiv:1812.11619 [quant-ph]

Original

2018

Cited alongside, same era.

S. S. Tannu and M. K. Qureshi, “A case for variability-aware policies for nisq-era quantum computers,” (2018), arXiv:1805.10224 [quant-ph]

Original

2018

Cited alongside, same era.

W. Finigan, M. Cubeddu, T. Lively, J. Flick, and P. Narang, “Qubit allocation for noisy intermediate-scale quantum computers,” (2018), arXiv:1810.08291 [quant-ph]

Original

2018

Cited alongside, same era.

G. Li, Y. Ding, and Y. Xie, in Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems , ASPLOS ’19 (Association for Computing Machinery, New York, NY, USA, 2019) p. 1001–1014

2019

Later among the works it cites.

A. Cowtan, S. Dilkes, R. Duncan, A. Krajenbrink, W. Simmons, and S. Sivarajah, in 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019) , Leibniz International Proceedings in Informatics (LIPIcs), Vol. 135, edited by W. van Dam and L. Mancinska (Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2019) pp. 5:1–5:32

2019

Later among the works it cites.

M. Ghosh, N. Dey, D. Mitra, and A. Chakrabarti, Advances in Intelligent Systems and Computing 996

2020

Closest in time.

B. Nash, V. Gheorghiu, and M. Mosca, Quantum Science and Technology 5

2020

Closest in time.

M. Amy and V. Gheorghiu, Quantum Science and Technology 5

2020

Closest in time.

S. Sivarajah, S. Dilkes, A. Cowtan, W. Simmons, A. Edgington, and R. Duncan, Quantum Science and Technology (2020)

2020

Closest in time.

S. Nishio, Y. Pan, T. Satoh, H. Amano, and R. V. Meter, ACM Journal on Emerging Technologies in Computing Systems 16

2020

Closest in time.

D-Wave Systems Inc., “neal,” https://github.com/dwavesystems/dwave-neal (2020)

2020

Closest in time.

B. Tan, “Personal Communication,” (2020)

2020

Closest in time.