Asymptotically Optimal Quantum Circuits for d-level Systems
Stephen Bullock, Dianne M. O'Leary, G K. Brennen
As a qubit is a two-level system whose state space is spanned by and , so a qudit is a -level system whose state space is spanned by , , . Quantum computation has stimulated much recent interest in algorithmsfactoring unitary evolutions of an -qubit state space into component two-particle unitary evolutions. In theabsence of symmetry, Shende, Markov, and Bullock use Sard s theorem to prove that at least two-qubit unitaryevolutions are required, while Vartiainen, Moettoenen, and Salomaa (VMS) use the matrix factorization andGray codes in an optimal order construction involving two-particle evolutions. In this work, we note that Sard s theorem demands two-qudit unitary evolutions to construct a generic (symmetry-less) -qudit evolution.However, the VMS result applied to virtual qubits only recovers optimal order in the case that is a power oftwo. We further construct a decomposition for multi-level quantum logics, proving a sharp asymptoticof two-qudit gates and thus closing the complexity question for all -level systems ( finite.) Gray codesare not required.
, O'Leary, D.
and Brennen, G.
Asymptotically Optimal Quantum Circuits for d-level Systems, Physical Review Letters, [online], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=150903
(Accessed March 5, 2024)