title: Computational speed-up with a single qudit.
abstract: Quantum algorithms are known for providing more efficient solutions to certain computational tasks than any corresponding classical algorithm. Here we show that a single qudit is sufficient to implement an oracle based quantum algorithm, which can solve a black-box problem faster than any classical algorithm. For 2d permutation functions defined on a set of d elements, deciding whether a given permutation is even or odd, requires evaluation of the function for at least two elements. We demonstrate that a quantum circuit with a single qudit can determine the parity of the permutation with only one evaluation of the function. Our algorithm provides an example for quantum computation without entanglement since it makes use of the pure state of a qudit. We also present an experimental realization of the proposed quantum algorithm with a quadrupolar nuclear magnetic resonance using a single four-level quantum system, i.e., a ququart.
authors.affiliation: Faculty of Engineering and Natural Sciences, Sabanci University, Tuzla, Istanbul, 34956, Turkey.
authors.forename: Z
authors.initials: Z
authors.lastname: Gedik
authors.affiliation: Instituto de Física de São Carlos, Universidade de São Paulo, Caixa Postal 369, 13560-970 São Carlos, São Paulo, Brazil.
authors.forename: I A
authors.initials: IA
authors.lastname: Silva
authors.affiliation: Faculty of Engineering and Natural Sciences, Sabanci University, Tuzla, Istanbul, 34956, Turkey.
authors.forename: B
authors.initials: B
authors.lastname: Çakmak
authors.affiliation: Faculdade de Ciências, UNESP - Universidade Estadual Paulista, Bauru, São Paulo, 17033-360, Brazil.|Turku Center for Quantum Physics, Department of Physics and Astronomy, University of Turku, FIN-20014 Turku, Finland.
authors.forename: G
authors.initials: G
authors.lastname: Karpat
authors.affiliation: Instituto de Física de São Carlos, Universidade de São Paulo, Caixa Postal 369, 13560-970 São Carlos, São Paulo, Brazil.
authors.forename: E L G
authors.initials: EL
authors.lastname: Vidoto
authors.affiliation: Instituto de Física de São Carlos, Universidade de São Paulo, Caixa Postal 369, 13560-970 São Carlos, São Paulo, Brazil.
authors.forename: D O
authors.initials: DO
authors.lastname: Soares-Pinto
authors.affiliation: Instituto de Física de São Carlos, Universidade de São Paulo, Caixa Postal 369, 13560-970 São Carlos, São Paulo, Brazil.
authors.forename: E R
authors.initials: ER
authors.lastname: deAzevedo
authors.affiliation: Faculdade de Ciências, UNESP - Universidade Estadual Paulista, Bauru, São Paulo, 17033-360, Brazil.
authors.forename: F F
authors.initials: FF
authors.lastname: Fanchini