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.

Combined version of arXiv:1403.5861 [quant-ph] and arXiv:1406.3579 [quant-ph]

References in corpus (7)

• Contextuality supplies the magic for quantum computation
• A simple test for hidden variables in spin-1 system
• Quantum Computing with NMR
• Universal quantum computation with little entanglement
• Determining the parity of a permutation using an experimental NMR qutrit
• Linear optical demonstration of quantum speed-up with a single qudit
• Demonstration of quantum permutation algorithm with a single photon ququart

Cited by in corpus (61)

• Qudits and high-dimensional quantum computing
• Ultracold polar molecules as qudits
• Qutrit randomized benchmarking
• High-Fidelity Qutrit Entangling Gates for Superconducting Circuits
• Native qudit entanglement in a trapped ion quantum processor
• Performing SU($d$) operations and rudimentary algorithms in a superconducting transmon qudit for $d=3$ and $d=4$
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach
• Prospects for Simulating a Qudit Based Model of (1+1)d Scalar QED
• Quantum capacity analysis of multi-level amplitude damping channels
• Complete unitary qutrit control in ultracold atoms
• Optimization and experimental realization of the quantum permutation algorithm
• Asymptotically Improved Circuit for $d$-ary Grover's Algorithm with Advanced Decomposition of $n$-qudit Toffoli Gate
• Quantum-polarization state tomography
• A hybrid quantum repeater for qudits
• Hybrid controlled-SUM gate with one superconducting qutrit and one cat-state qutrit and application in hybrid entangled state preparation
• Emulating two qubits with a four-level transmon qudit for variational quantum algorithms
• Exploring quantum thermodynamics with NMR
• Quantum Simulations of SO(5) Many-Fermion Systems using Qudits
• Multilevel quantum thermodynamic swap engines
• Quantum Computing with Endohedral Fullerenes
• Experimental demonstration of quantum contextuality on an NMR qutrit
• Magic informationally complete POVMs with permutations
• Qutrit and Qubit Circuits for Three-Flavor Collective Neutrino Oscillations
• Experimental quantum tomography assisted by multiply symmetric states in higher dimensions
• Demonstration of quantum permutation algorithm with a single photon ququart
• The magic of universal quantum computing with permutations
• Majorana representation, qutrit Hilbert space and NMR implementation of qutrit gates
• A hybrid-qudit representation of digital RGB images
• $i$-QER: An Intelligent Approach towards Quantum Error Reduction
• Variational Quantum Multi-Objective Optimization
• Partially Coherent Direct Sum Channels
• QuDiet: A Classical Simulation Platform for Qubit-Qudit Hybrid Quantum Systems
• Optimal control of hybrid qubits: implementing the quantum permutation algorithm
• Time-Efficient Qudit Gates through Incremental Pulse Re-seeding
• Adaptive Compilation of Multi-Level Quantum Operations
• Information processing using three-qubit and qubit-qutrit encodings of noncomposite quantum systems
• Quantum Measurement Classification with Qudits
• Pauli-based model of quantum computation with higher-dimensional systems
• Qubit representation of qudit states: correlations and state reconstruction
• Implementing positive-operator-valued-measurement elements in photonic circuits for performing minimum quantum state tomography of path qudits
• Multi-qudit states generated by unitary braid quantum gates based on Temperley-Lieb algebra
• Compilation of Entangling Gates for High-Dimensional Quantum Systems
• Cat-state generation and stabilization for a nuclear spin through electric quadrupole interaction
• Coherence behavior of strongly coupled bosonic modes
• Scaling W state circuits in the qudit Clifford hierarchy
• Negativity-Mutual Information conversion and coherence in two-coupled harmonic oscillators
• Quantum algorithm for learning secret strings and its experimental demonstration
• Steered discrete-time quantum walks for engineering of quantum states
• The Synthetic Hilbert Space of Laser-Driven Free-Electrons
• QFT based quantum arithmetic logic unit on IBM quantum computer
• Dissipative phase transition: from qubits to qudits
• N-qubit universal quantum logic with a photonic qudit and O(N) linear optics elements
• Moving Quantum States without SWAP via Intermediate Higher Dimensional Qudits
• Time-dependent Rabi frequencies to protect quantum operations on an atomic qutrit by continuous dynamical decoupling
• MUB-like structures and tomographic reconstruction for N-ququart systems
• Bounding the Classical Capacity of Multilevel Damping Quantum Channels
• Quantum computation with charge-and-color permuting twists in qudit color codes
• Physically motivated decompositions of single-qutrit gates
• Transversal AND in Quantum Codes
• Quantum Advantage in Identifying the Parity of Permutations with Certainty
• Efficient Implementation of a Single-Qutrit Gate Set via Coherent Control