A Conditional Route to BQP = P = NP: Canonical Exact-Cover States and a QAOA Attachment | IJCT Volume 13 – Issue 5 | IJCT-V13I5P49
International Journal of Computer Techniques
ISSN 2394-2231
Author
Michael S. Yang
Abstract
This article formalizes the relationship between a previously published HKD-infinity transfer–distillation reduction for Exact Cover by 3-Sets and a quantum approximate optimization attachment. The classical reduction is exact but conditional: if the number of distinct canonical residual states is polynomially bounded for every input, then Exact Cover by 3-Sets is in polynomial time and hence P = NP. A quadratic unconstrained binary optimization model permits candidate-state or dictionary selection to be processed by the Quantum Approximate Optimization Algorithm. That attachment does not establish a quantum speedup and does not imply BQP ⊆ P. We therefore state the strongest valid combined result: the polynomial canonical-state hypothesis together with an independent efficient classical-simulation hypothesis for bounded-error quantum computation implies BQP = P = NP. Verbatim Python code performs exhaustive finite-instance checks of the exact-cover recursion, and a SymPy program verifies the algebraic QUBO-to-Ising substitution and the logical dependency of the class equality. These checks improve auditability but cannot decide either universal hypothesis. The contribution is a falsifiable separation of the classical quotient-growth obligation, the quantum-simulation obligation, and the finite computations that bear on neither as a proof.
Keywords
computational complexity; exact cover; quantum algorithms; state-space reduction; symbolic verification.
Conclusion
The precise defensible result is conditional. The prior HKD-infinity work reduces P = NP to a universal polynomial bound on exact canonical X3C states. The QAOA attachment sup-plies a valid quantum optimization formulation but no proof that BQP ⊆ P. Assuming both missing statements does yield BQP = P = NP. The included exhaustive and symbolic pro-grams make the finite algebra and solver behavior reproducible while explicitly leaving the two universal obligations open.
References
[1] L. M. Adleman, J. DeMarrais, and M.-D. A. Huang, “Quantum computability,” SIAM Journal on Com-puting, vol. 26, no. 5, pp. 1524–1540, 1997, doi: 10.1137/S0097539795293639.
[2] E. Bernstein and U. Vazirani, “Quantum complexity the-ory,” SIAM Journal on Computing, vol. 26, no. 5, pp. 1411–1473, 1997, doi: 10.1137/S0097539796300921.
[3] E. Farhi, J. Goldstone, and S. Gutmann, “A quantum approximate optimization algorithm,” arXiv:1411.4028, 2014. [Online]. Available: https://arxiv.org/abs/ 1411.4028.
[4]M. R. Garey and D. S. Johnson, Computers and In-tractability: A Guide to the Theory of NP-Completeness. San Francisco, CA, USA: W. H. Freeman, 1979.
[5] J. Watrous, “Quantum computational complexity,” in Encyclopedia of Complexity and Systems Science, R. A. Meyers, Ed. New York, NY, USA: Springer, 2009, pp. 7174–7201, doi: 10.1007/978-0-387-30440-3_428.
[6] J. Weidenfeller et al., “Scaling of the Quantum Approxi-mate Optimization Algorithm on superconducting qubit based hardware,” Quantum, vol. 6, p. 870, 2022, doi: 10.22331/q-2022-12-07-870.
M. S. Yang, “HKD-infinity transfer–distillation reduc-tion for exact cover,” International Journal of Computer Techniques, vol. 13, no. 5, pp. 345–351, 2026. [Online]. Available: IJCT article PDF.
How to Cite This Paper
Michael S. Yang (2026). A Conditional Route to BQP = P = NP: Canonical Exact-Cover States and a QAOA Attachment. International Journal of Computer Techniques, 13(5). ISSN: 2394-2231.
Related Posts:
