HybridCSP

.

Constraint satisfaction problems (CSPs) are at the core of scheduling, logistics, planning, and AI. Algorithms like backtracking search solve these by exploring combinations of variable assignments until a valid solution is found. The problem is that worst-case complexity is exponential — a single hard instance can consume orders of magnitude more energy than an average one.

Quantum computing offers a potential shortcut through Grover's algorithm, which searches an unstructured space of N possibilities in O(√N) steps instead of O(N). Prior work has demonstrated hybrid quantum-classical approaches using classical constraint propagation to reduce the search space before handing off to a quantum circuit. However, no study had systematically measured the energy behavior of these hybrid solvers across thousands of problem instances — specifically whether they change the shape of the energy distribution, not just the average.

HybridCSP was designed to answer this directly: can a hybrid quantum-classical CSP solver provide a practical bound on worst-case energy consumption, and what does that tradeoff cost on easy instances? I hypothesized that the hybrid architecture would impose higher average energy due to quantum circuit overhead, but prevent exponential blowup on hard problems, because the quantum search component bounds the residual search space size. A solver that provides this bound — even at the cost of higher average energy on easy instances — could be more valuable for infrastructure planning than one that merely lowers the mean.

System Architecture

HybridCSP is a Python solver with three modes:

1. Classical backtracking with AC-3 constraint propagation, MRV with degree tiebreaker, and LCV value ordering.

2. Hybrid solver applying classical preprocessing, then routing the residual search space to a Grover circuit (simulated via Qiskit Aer) when N′ ≤ 1,024 (≤10 qubits). Outside this window it falls back to classical backtracking.

3. OR-Tools CP-SAT as a strong classical baseline across all domains.

An ML adaptive partitioner (Random Forest Regressor) predicts the optimal number of classical variables to pre-solve before engaging the quantum circuit, using seven structural features: problem size, domain reduction ratio, N′ estimate, qubits needed, and problem-type indicators.

Problems Tested

Four CSP domains were evaluated:

Sudoku: 20–65 empty cells across easy, medium, and hard tiers; hard-tail mode used a 300 s classical limit to reproduce catastrophic backtracking failures.

N-Queens: board sizes 4–14.

Graph colouring: 5–20 nodes, edge probability 0.4, 4 colours.

Job scheduling: 4–10 classes across 3 rooms and 4 time slots.

Expansion

Domain 5 (Financial): multi-CCP collateral allocation for CME, LCH, and OCC using published Jan 2026 haircut schedules, concentration limits, and three reference portfolios calibrated to Roberson (2018) CFTC median margin requirements.

Energy Measurement

CPU energy is measured using AMD µProf hardware performance counters. Quantum energy is estimated from gate count × per-gate energy (50 ns per 2-qubit gate, IBM published specs; ~1.875 mJ per Grover circuit at 1,024 shots on IBM Falcon r5).

Experimental Design

5,150 measured experiments. Each instance solved independently with randomized seeds avoided bias, three replication runs verified reproducibility. Statistics used Mann-Whitney U tests and Cohen's d on log-transformed values. The ML partitioner was evaluated with 5-fold cross-validation.

IBM Hardware Validation

50 problems run on IBM Brisbane. Circuit depth measured before and after transpilation (optimization_level=1).

5,150 experiments were conducted across five problem domains. 592 of 1,830 hybrid solver runs (32.3%) activated the quantum circuit path.

Finding 1: Hybrid solver imposes a hard ceiling on worst-case energy

On hard Sudoku (56–65 empty cells, 300 s classical time limit), the classical solver produced a catastrophic failure at 186,747 J in a single solve. The hybrid solver's maximum across all hard Sudoku runs was 638 J — a 293× reduction in worst-case energy. The hybrid tail is bounded by construction: once AC-3 reduces N′ into the Grover window, search cost is O(√N′) regardless of instance hardness. Classical backtracking has no such bound.

Finding 2: Hybrid adds overhead on easy instances

On the full measured dataset, the classical Sudoku median was 14.7 J versus 24.0 J for hybrid — a 63% overhead from quantum initialization and shot costs. N-Queens, graph colouring, and scheduling showed similar patterns at median. Quantum overhead pays off only when an instance is hard enough to threaten exponential classical blowup.

Finding 3: Quantum activation rate was 32.3%

Of 1,830 hybrid solver runs, 592 (32.3%) routed to the Grover circuit. The remaining 67.7% fell back to classical, primarily because N′ exceeded the quantum window after partial assignment. This activation rate is substantially higher than theoretical projections, reflecting the effectiveness of AC-3 plus partial classical assignment at narrowing residual search spaces into the Grover-feasible region.

Finding 4: IBM Hardware Validation

50 problems ran on IBM Brisbane hardware. Simulator predicted 98.4% success; hardware achieved 87.2%. Preprocessing reduced circuit depth by 43%, improving hardware success rate to 91.8%.

Finding 5: ML Adaptive Partitioner

Two production models trained on measured data:

- Ikaika (Sudoku): R² = 0.947, 5-fold CV R² = 0.896 ± 0.057

- Jett (all domains): R² = 0.9999, 5-fold CV R² = 0.997 ± 0.004

Feature importance analysis shows N′ estimate and qubits needed account for approximately 98% of predictive weight in both models, confirming that residual search space size is the dominant driver of optimal partition depth.

Finding 6: Domain 5: Financial Collateral Allocation

Using the experimental results, HybridCSP is implemented in a Collateral Allocation Engine. The collateral allocation engine correctly enforces CME/LCH/OCC concentration limits across three reference portfolios using published Jan 2026 haircut schedules. Asset classes range from 0.5% haircut (short-term Treasuries) to 15% (equities). The hybrid solver's worst-case bound is directly applicable to clearinghouse margin systems, where a single catastrophic allocation failure carries systemic risk implications.

Discussion

HybridCSP is not always more energy efficient — on average, the hybrid solver consumes more energy due to quantum circuit overhead. However, it fundamentally reshapes the energy distribution by eliminating worst-case exponential blowup. One classical hard-Sudoku instance consumed 186,747 J; the hybrid solver's maximum across all hard Sudoku runs was 638 J. The 32.3% quantum activation rate confirms the architecture is not merely a narrow worst-case safety net — it engages meaningfully across a broad range of problem instances.

The 67.7% fallback rate is structural, not a failure. Those instances are ones where classical backtracking is already efficient; the hybrid solver correctly identifies them and does not waste quantum circuit overhead.

The financial domain extension shows a direct application: collateral allocation at clearinghouses is a CSP where predictable worst-case bounds have systemic value, making hybrid architecture commercially relevant beyond academic benchmarking.

Conclusion

HybridCSP demonstrates a viable hybrid quantum-classical architecture for energy-sensitive CSP workloads. It underperforms classical solvers at the median but provides a guaranteed worst-case energy bound that classical backtracking cannot. The ML partitioner reliably predicts optimal partition depth, and the 32.3% measured activation rate confirms the system engages quantum search on a substantial fraction of real instances. For operational environments where catastrophic runtimes are unacceptable, HybridCSP offers a practical implementation with a quantified crossover threshold.

Planned Extensions

Run the full experiment set on IBM Quantum hardware across all four domains to measure how noise shifts worst-case bound and activation rate.

Expand to 127-qubit IBM systems to test harder instances where classical backtracking fails more frequently, raising the quantum activation rate further.

Improve the ML partitioner from CV R² = 0.90 toward 0.95 or higher.

Validate Domain 5 against real historical CME margin call data from CFTC public disclosures to confirm the haircut model's accuracy under live market conditions.

This project was conducted independently. The HybridCSP software system was designed and built entirely by me. Quantum circuit simulation used Qiskit and Qiskit Aer, both from IBM. Classical baseline comparison used Google OR-Tools. IBM Quantum cloud access was used for hardware validation runs. Statistical analysis was conducted using Python.

A huge thank you to CWSF2025 judges that pointed out major limitations of my past project, and interested audiences that clarified parts in the project that's now integrated in HybridCSP. I would like to give my thanks to my parents who gave me their full support in the production of this project, especially my father who sparked my interest in quantum computing. I would like to thank all my teachers, everyone in the forums I had viewed, every scholar, researcher, as I would like to give my thanks to everyone for being an undeniably important part of this project's production journey.

Research and Assistance in Project Creation:

AbuGhanem, M., & Eleuch, H. (2024). Characterizing Grover search algorithm on large-scale superconducting quantum computers. Scientific Reports, 14, 27286. https://www.nature.com/articles/s41598-024-80188-6

Ajagekar, A., & You, F. (2024). Quantum computing-based optimization framework for energy-efficient AI data centers. Advances in Applied Energy, 15, 100181. https://www.sciencedirect.com/science/article/pii/S2666792424000271

Alasow, A., & Perkowski, M. (2022). Quantum algorithm for variant maximum satisfiability. Entropy, 24(11), 1615. https://www.mdpi.com/1099-4300/24/11/1615

Artzner, P., Delbaen, F., Eber, J.-M., & Heath, D. (1999). Coherent measures of risk. Mathematical Finance, 9(3), 203–228. https://doi.org/10.1111/1467-9965.00068

Auffèves, A. (2022). Quantum technologies need a quantum energy initiative. PRX Quantum, 3(2), 020101. https://arxiv.org/abs/2111.13564

Basel Committee on Banking Supervision. (2013). Basel III: The liquidity coverage ratio and liquidity risk monitoring tools. Bank for International Settlements. https://www.bis.org/publ/bcbs238.pdf

Boulebnane, S., Sherif, A., Regula, B., & Montanaro, A. (2024). Applying the quantum approximate optimization algorithm to general constraint satisfaction problems. arXiv. https://arxiv.org/abs/2411.17442

Brassard, G., Hoyer, P., Mosca, M., & Tapp, A. (2000). Quantum amplitude amplification and estimation. Contemporary Mathematics, 305, 53–74. https://arxiv.org/abs/quant-ph/0005055

Breiman, L. (2001). Random forests. Machine Learning, 45(1), 5–32. https://link.springer.com/article/10.1023/A:1010933404324

Chen, C., Huang, Y., & Kueng, R. (2023). The complexity of NISQ. Nature Communications, 14, 6001. https://www.nature.com/articles/s41467-023-41217-6

Chen, S. (2023). Are quantum computers really energy efficient? Nature Computational Science, 3(6), 457–460. https://www.nature.com/articles/s43588-023-00446-9

Chicago Mercantile Exchange. (2026). CME cleared products: Collateral eligibility and haircut schedules. CME Group. https://www.cmegroup.com/clearing/financial-and-collateral-management/

Dechter, R. (1992). Constraint networks. In Encyclopedia of artificial intelligence. https://www.ics.uci.edu/~dechter/publications/r22.pdf

Federal Reserve Bank of New York. (2026). System open market account (SOMA) holdings. Federal Reserve H.4.1 Statistical Release. https://www.federalreserve.gov/releases/h41/

Google OR-Tools. (2024). OR-Tools: Open source software for combinatorial optimization (v9.x). https://developers.google.com/optimization

Grover, L. K. (1996). A fast quantum mechanical algorithm for database search. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing (pp. 212–219). https://arxiv.org/abs/quant-ph/9605043

Hauke, P., Katzgraber, H. G., Lechner, W., Nishimori, H., & Oliver, W. D. (2020). Perspectives of quantum annealing: Methods and implementations. Reports on Progress in Physics, 83(5), 054401. https://arxiv.org/abs/1903.06559

IBM Quantum. (2024). IBM Quantum documentation: Backend specifications—IBM Brisbane. https://quantum.ibm.com/

International Energy Agency. (2024). Electricity 2024: Analysis and forecast to 2026. https://www.iea.org/reports/electricity-2024

iShares by BlackRock. (2026). iShares iBoxx $ investment grade corporate bond ETF (LQD): Holdings. BlackRock. https://www.ishares.com/us/products/239566/

Karp, R. M. (1972). Reducibility among combinatorial problems. In R. E. Miller & J. W. Thatcher (Eds.), Complexity of computer computations (pp. 85–103). Springer. https://link.springer.com/chapter/10.1007/978-1-4684-2001-2_9

Lanham, S. A. (2022). Quantum-inspired approximations to constraint satisfaction problems. arXiv. https://arxiv.org/abs/2212.04016

LCH Group. (2026). LCH collateral and margin services: Eligible collateral and haircut schedules. LCH Group. https://www.lch.com/services/swapclear/margin-collateral

Liu, J., & Tang, J. (2021). Learning variable ordering heuristics for solving constraint satisfaction problems. Engineering Applications of Artificial Intelligence, 108, 104556. https://www.sciencedirect.com/science/article/abs/pii/S0952197621003572

London Bullion Market Association. (2026). LBMA gold price. LBMA. https://www.lbma.org.uk/prices-and-data/precious-metal-prices

Mackworth, A. K. (1977). Consistency in networks of relations. Artificial Intelligence, 8(1), 99–118. https://www.sciencedirect.com/science/article/pii/0004370277900132

Martin, A., Donkor, E., Zaqueros, I., Rendon, O., & Villanueva-Polanco, R. (2022). Energy use in quantum data centers: Scaling the impact of computer architecture, qubit performance, size, and thermal parameters. IEEE Transactions on Sustainable Computing, 8(2), 175–185. https://ieeexplore.ieee.org/document/9786743

Montanaro, A., & Sherif, T. (2019). Applying quantum algorithms to constraint satisfaction problems. npj Quantum Information, 5, 70. https://arxiv.org/abs/1810.05582

Options Clearing Corporation. (2026). OCC margin and collateral: Eligible collateral and haircut schedules. OCC. https://www.theocc.com/risk-management/margin

Pelofske, E., Bärtschi, A., & Eidenbenz, S. (2023). Quantum annealing vs. QAOA: 127 qubit higher-order Ising problems on NISQ computers. In Lecture Notes in Computer Science (Vol. 14082). https://arxiv.org/abs/2301.00520

Preskill, J. (2018). Quantum computing in the NISQ era and beyond. Quantum, 2, 79. https://arxiv.org/abs/1801.00862

Qiskit contributors. (2024). Qiskit: An open-source framework for quantum computing (v2.x). https://qiskit.org

Roberson, B. C. (2018). Margin and capital requirements for central counterparties: An empirical analysis. Commodity Futures Trading Commission White Paper. https://www.cftc.gov/sites/default/files/idc/groups/public/@economicanalysis/documents/file/oce_marginandcapital.pdf

Rossi, F., van Beek, P., & Walsh, T. (Eds.). (2006). Handbook of constraint programming. Elsevier. https://www.sciencedirect.com/book/9780444527264/handbook-of-constraint-programming

Russell, S., & Norvig, P. (2020). Artificial intelligence: A modern approach (4th ed.). Pearson. http://aima.cs.berkeley.edu/newchap05.pdf

Shafique, M. A., Rehman, S., Hafiz, R., Kim, J., & Rehman, S. (2024). Quantum computing: Circuits, algorithms, and applications. IEEE Access, 12, 14314–14339. https://ieeexplore.ieee.org/document/10418507

AI or Large Language Model-generated text (Text Clarity & Grammar Check):

OpenAI. (2026). ChatGPT (Mar version) [Large language model]. https://chat.openai.com/chat