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.

arXiv commentupdated text and figures

References in corpus (31)

• SciPy 1.0--Fundamental Algorithms for Scientific Computing in Python
• Quantum Computing in the NISQ era and beyond
• Ising formulations of many NP problems
• Dynamical Decoupling of Open Quantum Systems
• Dynamical suppression of decoherence in two-state quantum systems
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• Self-Verifying Variational Quantum Simulation of the Lattice Schwinger Model
• Perspectives of quantum annealing: Methods and implementations
• 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
• Review of Decoherence Free Subspaces, Noiseless Subsystems, and Dynamical Decoupling
• Near-optimal quantum circuit for Grover's unstructured search using a transverse field
• Qutrit randomized benchmarking
• Benchmarking the Quantum Approximate Optimization Algorithm
• Hybrid quantum-classical algorithms for approximate graph coloring
• Quantum Computing with Circular Rydberg Atoms
• On the representation of Boolean and real functions as Hamiltonians for quantum computing
• Domain wall encoding of discrete variables for quantum annealing and QAOA
• Quantum Phase Estimation with Time-Frequency Qudits in a Single Photon
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach
• Determining the parity of a permutation using an experimental NMR qutrit
• Low depth mechanisms for quantum optimization
• To quantum or not to quantum: towards algorithm selection in near-term quantum optimization
• Probing Entanglement in Adiabatic Quantum Optimization with Trapped Ions
• Number Partitioning with Grover's Algorithm in Central Spin Systems
• Universal quantum control in irreducible state-space sectors: application to bosonic and spin-boson 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