Quantum approximate optimization algorithm for qudit systems

Abstract

A frequent starting point of quantum computation platforms are two-state quantum systems, i.e., qubits. However, in the context of integer optimization problems, relevant to scheduling optimization and operations research, it is often more resource-efficient to employ quantum systems with more than two basis states, so-called qudits. Here, we discuss the quantum approximate optimization algorithm (QAOA) for qudit systems. We illustrate how the QAOA can be used to formulate a variety of integer optimization problems such as graph coloring problems or electric vehicle (EV) charging optimization. In addition, we comment on the implementation of constraints and describe three methods to include these into a quantum circuit of a QAOA by penalty contributions to the cost Hamiltonian, conditional gates using ancilla qubits, and a dynamical decoupling strategy. Finally, as a showcase of qudit-based QAOA, we present numerical results for a charging optimization problem mapped onto a max-$k$-graph coloring problem. Our work illustrates the flexibility of qudit systems to solve integer optimization problems.

updated text and figures

References in corpus (14)

• Qudits and high-dimensional quantum computing
• Fisher Information and entanglement of non-Gaussian spin states
• A universal qudit quantum processor with trapped ions
• Quantum Annealing for Industry Applications: Introduction and Review
• Programmable Interactions and Emergent Geometry in an Atomic Array
• Qutrit randomized benchmarking
• Hybrid quantum-classical algorithms for approximate graph coloring
• Quantum Computing with Circular Rydberg Atoms
• Determining the parity of a permutation using an experimental NMR qutrit
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach
• Low depth mechanisms for quantum optimization
• Probing Entanglement in Adiabatic Quantum Optimization with Trapped Ions
• Number Partitioning with Grover's Algorithm in Central Spin Systems
• Practical Verification of Quantum Properties in Quantum Approximate Optimization Runs

Cited by in corpus (15)

• Exploring Ququart Computation on a Transmon using Optimal Control
• Data re-uploading with a single qudit
• Encoding trade-offs and design toolkits in quantum algorithms for discrete optimization: coloring, routing, scheduling, and other problems
• Variational Quantum Multi-Objective Optimization
• Characterization of variational quantum algorithms using free fermions
• Qudit-inspired optimization for graph coloring
• QuForge: A Library for Qudits Simulation
• Inequality constraints in variational quantum circuits with qudits
• Efficient fidelity estimation: Alternative derivation and related applications
• IF-QAOA: A Penalty-Free Approach to Accelerating Constrained Quantum Optimization
• Symmetry-enhanced Counterdiabatic Quantum Algorithm for Qudits
• Graph Coloring via Quantum Optimization on a Rydberg-Qudit Atom Array
• Entanglement swapping for partially entangled qudits and the role of quantum complementarity
• Efficient QAOA Architecture for Solving Multi-Constrained Optimization Problems
• Quantum approximate optimization of finite-state bosonic systems