Flag Qubits Generate Equal Superposition of Feasible States in Quadratic Optimization

Quadratic constrained binary optimisation problems, which represent a significant challenge for modern computing, often arise in fields ranging from machine learning to logistics. Anthony Wilkie from the University of Tennessee at Knoxville, Alexander DeLise from Florida State University, and Andrew Del Real from Carthage College, alongside their colleagues, present a new method for tackling these complex problems by creating a balanced superposition of states that inherently satisfy the given constraints. This innovative approach utilises additional quantum bits, known as flag qubits, to effectively identify and avoid states that violate the problem’s rules, paving the way for more efficient algorithms. Testing reveals the method generates feasible solutions with high accuracy, and crucially, significantly improves the performance of a quantum approximate optimisation algorithm when used as a starting point, offering a promising step towards solving previously intractable optimisation challenges.

This work develops a variational approach that creates an equal superposition of quantum states which satisfy constraints in a QCBO. The method relies on flag qubits, one per constraint, to identify when a constraint is violated or not. The resulting equal superposition can be used as an initial state for quantum algorithms that solve QUBOs/QCBOs, such as Grover’s search algorithm or the quantum approximate optimisation algorithm (QAOA).

Constraint Enforcement via Quantum Gadgets

This research explores a novel approach to solving constrained combinatorial optimisation problems using the Quantum Approximate Optimisation Algorithm (QAOA). The core idea is to create constraint gadgets, specific quantum circuits, that enforce constraints directly within the QAOA optimisation process, avoiding the need for penalty terms often used in traditional approaches. By directly enforcing constraints, the need for penalty terms is eliminated, potentially leading to more accurate and efficient optimisation. The research addresses the challenge of constrained optimisation, where many real-world problems have limitations on acceptable solutions.

Traditional QAOA implementations often use penalty terms in the cost function to account for these constraints, but these penalties can be difficult to tune and may hinder performance. The authors propose building quantum circuits (gadgets) that directly enforce the constraints, ensuring that only feasible solutions are considered during optimisation. The paper details how to construct these constraint gadgets based on the specific constraints of the problem and demonstrates the effectiveness of their approach on various benchmark problems, achieving competitive or superior performance compared to traditional methods. The open-source implementation further facilitates the adoption and advancement of this promising technology.

Feasible Solutions with Flag Qubit Encoding

Researchers have developed a new method for solving complex optimisation problems known as quadratic constrained binary optimisation (QCBOs). This new technique focuses on creating a quantum state representing only the feasible solutions, those that satisfy the given constraints, effectively narrowing the search space. The core of this method involves “flag qubits”, which act as indicators for each constraint. These qubits signal whether a potential solution violates a constraint or not. By using these flags, the researchers generate a quantum state where all feasible solutions are equally likely, creating a balanced starting point for optimisation algorithms.

Testing this approach with problems involving one or two linear constraints, the team achieved 98% accuracy in generating this equal superposition of feasible states. When integrated with a specific quantum algorithm called Grover-mixer QAOA (GM-QAOA), the method significantly increased the probability of finding the optimal solution compared to random guessing. The technique’s efficiency stems from its ability to focus on a reduced set of possibilities and work with a smaller quantum state, speeding up calculations.

Constraint Satisfaction via Balanced Superposition

This research introduces a new method for tackling quadratic constrained binary optimisation problems (QCBOs). The team developed a technique that generates an equal superposition of states, effectively focusing the quantum computation on solutions that satisfy the given constraints. This is achieved through the use of “flag qubits”, which indicate whether a constraint is met or violated, allowing the algorithm to prioritise feasible solutions from the outset. The method successfully creates this balanced superposition with a high degree of accuracy, averaging a 98% approximation ratio in tests involving linear inequality constraints. When integrated into a quantum optimisation algorithm called Grover-mixer QAOA (GM-QAOA), the method significantly improves the probability of finding the optimal solution compared to starting with a random state. The authors acknowledge that extending the method to handle more complex constraint types remains a challenge for future research.