Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE Wireless Communications Letters

RV-QUBO: Reduced-Variable QUBO for Decoding Short Systematic Polar Codes

Huayi Zhou, Yixiao Liu, Warren J. Gross, Chuan Zhang

Published Jan 1, 2026• 0 citations
Publisher

Abstract

Quantum annealer decoders have been proposed to unlock new potential by addressing channel decoding problems in quadratic unconstrained binary optimization (QUBO) form. However, the variables required by the existing node constraints in polar-QUBO decoding increase rapidly with the code length, resulting in prohibitively high computational complexity. In this letter, we propose reduced-variable QUBO (RV-QUBO) for short systematic polar codes, based on three key steps:1) applying equivalent generator matrix constraintsto replace the node constraints;2) introducing a common subexpression elimination approachto identify and replace recurringxorsubexpressions with new variables;3) imposing an extra length restriction on eachxorexpressionto balance the error-correction performance and the variable count. Numerical results indicate that the proposed scheme achieves a 73.60% reduction in variable count for$\mathcal {P}(32,28)$, while reducing the required iterations for convergence by 66.7%.

DOI
10.1109/lwc.2026.3716535

Related papers

Decoding of Polar Codes Using Quadratic Unconstrained Binary Optimization

Huayi Zhou, Ryan Seah, Marwan Jalaleddine +1 more

Polar codes encounter challenges in decoder complexity while preserving good error-correction properties. Instead of conventional decoders, a quantum annealer (QA) decoder has been proposed to explore untapped possibilities. For future QA applications, a crucial prerequisite is transforming the optimization problem into quadratic unconstrained binary optimization (QUBO) form. However, existing QUBO forms for polar decoding result in suboptimal frame error rate (FER) performance for codes exceeding 8 bits. This paper redesigns the QUBO form for polar decoding. We first introduce a novel receiver constraint modeled by the binary cross-entropy (BCE) function. Utilizing a simulated annealing (SA) solver with the proposed QUBO form with BCE (QUBO-BCE) achieves maximum-likelihood (ML) performance for a code length of 32 bits. Next, to reduce the number of variables, we remove the frozen variables and introduce a simplified QUBO-BCE form (SQUBO-BCE). Additionally, CRC polynomials are modelled into constraints in QUBO form, resulting in a CRC-aided SQUBO-BCE (CA-SQUBO-BCE) form for polar decoding to further enhance the FER. Numerical results demonstrate that SQUBO-BCE achieves ML performance and reduces up to 61.5% of variables compared to QUBO-BCE. Furthermore, the proposed CA-SQUBO-BCE achieves near CRC-aided ML performance. The proposed SQUBO-BCE requires the lowest number of SA processes to reach a specific FER.

IEEE Journal on Selected Areas in Communications•Jul 22, 2024•3 citations

Prime Factorization Using Partially Constrained Multiple Quantum Annealing With Analytical and Pattern-Based Variable Reduction

Xinyi Guo, Geguang Miao, Shinichi Nishizawa +2 more

Factorization of large semiprimes remains one of the most challenging problems for classical computers. Shor’s algorithm offers a quantum approach that reduces computational complexity, but its practical application is currently limited by hardware constraints. Meanwhile, as a provisional approach, quantum annealing (QA) has been explored through formulations of the quadratic unconstrained binary optimization (QUBO) problem. Among existing methods, the blockwise partial-product approach effectively reduced the QUBO variable count but was limited to semiprimes up to 21 bits. To extend factorization to larger semiprimes, this paper addresses key engineering challenges in constructing efficient QUBO formulations for prime factorization. We propose five techniques to reduce variable counts and improve scalability with current QA hardware: (1) dividing the problem into subproblems with partial constraints; (2) applying analytical reductions near the LSB; (3) applying analytical reductions near the MSB; (4) exploiting special patterns in semiprimes, with odd bit widths and long MSB-side zero sequences; and (5) balancing variable usage across both sides of the subproblem. Integrated into a QUBO converter, these methods enable stable factorization of semiprimes up to 47-bits within 20 seconds and can extend to special 2049-bit instances with 1001 consecutive MSB-side zeros.

IEEE Transactions on Computers•Jan 15, 2026•0 citations

New QUBO Transformations to Improve Quantum and Simulated Annealing Performance for Quadratic Knapsack

Nicolás Borrajo, Juan Ramírez, Farzam Nosrati +3 more

Recent advancements in quantum computing have demonstrated significant potential for solving combinatorial optimization problems, like the quadratic knapsack problem, a constrained binary optimization problem. However, current quantum and quantum-inspired algorithms often require transforming these constrained problems into an unconstrained form, known as Quadratic Unconstrained Binary Optimization (QUBO). Such transformations can significantly impact the algorithms’ speed and efficiency. In this study, we evaluate five existing transformation methods and propose four novel approaches. We assess all nine methods using Simulated Annealing and find that three of our approaches outperform existing methods in terms of execution time and the quality and quantity of feasible solutions found. Additionally, we tested these transformations on quantum annealers, which were unable to solve even small problem instances, due to limitations in connectivity and error rates. However, our results highlight the advantages of the new approaches, which reduce the total number of variables in the QUBO representation. This is a critical factor for enhanced performance on emerging quantum hardware, since it also reduces the required number of qubits and the embedding chain lengths.

International Conference on Agents and Artificial Intelligence (ICAART)•Jan 1, 2026•1 citation

New QUBO Transformations to Improve Quantum and Simulated Annealing Performance for Quadratic Knapsack

Nicolás Borrajo Carro, Juan Marcos Ramírez, Farzam Nosrati +3 more

Recent advancements in quantum computing have demonstrated significant potential for solving combinatorial optimization problems, like the quadratic knapsack problem, a constrained binary optimization problem. How- ever, current quantum and quantum-inspired algorithms often require transforming these constrained problems into an unconstrained form, known as Quadratic Unconstrained Binary Optimization (QUBO). Such transfor- mations can significantly impact the algorithms’ speed and efficiency. In this study, we evaluate five existing transformation methods and propose four novel approaches. We assess all nine methods using Simulated An- nealing and find that three of our approaches outperform existing methods in terms of execution time and the quality and quantity of feasible solutions found. Additionally, we tested these transformations on quantum annealers, which were unable to solve even small problem instances, due to limitations in connectivity and error rates. However, our results highlight the advantages of the new approaches, which reduce the total num- ber of variables in the QUBO representation. This is a critical factor for enhanced performance on emerging quantum hardware, since it also reduces the required number of qubits and the embedding chain lengths.

•May 27, 2025•0 citations

xSA: A Binary Cross-Entropy Simulated Annealing Polar Decoder

Ryan Seah, Huayi Zhou, Marwan Jalaleddine +1 more

Polar decoders such as successive-cancellation and successive-cancellation list decoders are limited by their sequential nature, which leads to a linear increase in latency with the codeword length. Heuristic based decoders such as quantum annealing have been proposed to overcome this limitation. However, these decoders have shown poor performance when decoding polar codes with more than eight bits. In this paper, we developed new meta-heuristic based polar decoder, called xSA, which uses a new receiver constraint modeled by the binary cross-entropy function. We also propose a method to determine the weights used in a quadratic unconstrained binary optimization (QUBO) function. The polar code is assumed to have been sent across an AWGN channel and we conducted our experiments and simulations using PyQUBO and dwave-neal. Our results show that xSA is able to decode codes of length 16 and 32 with a near-ML FER performance, presenting itself as a promising alternative to traditional polar decoders for real world applications and next generation cellular communications.

International Symposium on Turbo Codes and Iterative Information Processing•Sep 4, 2023•3 citations

REDUCING DISCRETE OPTIMIZATION PROBLEMS TO THE QUBO FORM

A.M. Semenov, S.R. Usmanov, Aleksey K. Fedorov

Practical discrete optimization problems often contain multidimensional arrays of variables with linear constraints, which complicates their conversion to QUBO (quadratic unconstrained binary optimization) form. The article proposes a systematic approach to transforming such problems, which includes three key steps: the transition from a multidimensional representation of variables to a one-dimensional one using the Kronecker product of matrices, the reduction of mixed variables to binary ones, and the introduction of linear constraints into the objective function through quadratic penalties. Explicit computational formulas are obtained for each stage, simplifying their software implementation. The developed method is illustrated with examples from graph theory and combinatorial optimization, including classical formulations, confirming its universality. The results of the article allow standardizing the process of adapting problems for solving on quantum annealing algorithms (e.g., D-Wave) and classical QUBO solvers.

Problems of Information Transmission•Jan 1, 2025•2 citations
Quantum annealer decoders have been proposed to unlock new potential by addressing channel decoding problems in quadratic unconstrained binary optimization (QUBO) form. However, the variables required by the existing node constraints in polar-QUBO decoding increase rapidly with the code length, resulting in prohibitively high computational complexity. In this letter, we propose reduced-variable QUBO (RV-QUBO) for short systematic polar codes, based on three key steps:1) applying equivalent generator matrix constraintsto replace the node constraints;2) introducing a common subexpression elimination approachto identify and replace recurringxorsubexpressions with new variables;3) imposing an extra length restriction on eachxorexpressionto balance the error-correction performance and the variable count. Numerical results indicate that the proposed scheme achieves a 73.60% reduction in variable count forP(32,28)\mathcal {P}(32,28)P(32,28), while reducing the required iterations for convergence by 66.7%.
Polar codes encounter challenges in decoder complexity while preserving good error-correction properties. Instead of conventional decoders, a quantum annealer (QA) decoder has been proposed to explore untapped possibilities. For future QA applications, a crucial prerequisite is transforming the optimization problem into quadratic unconstrained binary optimization (QUBO) form. However, existing QUBO forms for polar decoding result in suboptimal frame error rate (FER) performance for codes exceeding 8 bits. This paper redesigns the QUBO form for polar decoding. We first introduce a novel receiver constraint modeled by the binary cross-entropy (BCE) function. Utilizing a simulated annealing (SA) solver with the proposed QUBO form with BCE (QUBO-BCE) achieves maximum-likelihood (ML) performance for a code length of 32 bits. Next, to reduce the number of variables, we remove the frozen variables and introduce a simplified QUBO-BCE form (SQUBO-BCE). Additionally, CRC polynomials are modelled into constraints in QUBO form, resulting in a CRC-aided SQUBO-BCE (CA-SQUBO-BCE) form for polar decoding to further enhance the FER. Numerical results demonstrate that SQUBO-BCE achieves ML performance and reduces up to 61.5% of variables compared to QUBO-BCE. Furthermore, the proposed CA-SQUBO-BCE achieves near CRC-aided ML performance. The proposed SQUBO-BCE requires the lowest number of SA processes to reach a specific FER.
Factorization of large semiprimes remains one of the most challenging problems for classical computers. Shor’s algorithm offers a quantum approach that reduces computational complexity, but its practical application is currently limited by hardware constraints. Meanwhile, as a provisional approach, quantum annealing (QA) has been explored through formulations of the quadratic unconstrained binary optimization (QUBO) problem. Among existing methods, the blockwise partial-product approach effectively reduced the QUBO variable count but was limited to semiprimes up to 21 bits. To extend factorization to larger semiprimes, this paper addresses key engineering challenges in constructing efficient QUBO formulations for prime factorization. We propose five techniques to reduce variable counts and improve scalability with current QA hardware: (1) dividing the problem into subproblems with partial constraints; (2) applying analytical reductions near the LSB; (3) applying analytical reductions near the MSB; (4) exploiting special patterns in semiprimes, with odd bit widths and long MSB-side zero sequences; and (5) balancing variable usage across both sides of the subproblem. Integrated into a QUBO converter, these methods enable stable factorization of semiprimes up to 47-bits within 20 seconds and can extend to special 2049-bit instances with 1001 consecutive MSB-side zeros.
Recent advancements in quantum computing have demonstrated significant potential for solving combinatorial optimization problems, like the quadratic knapsack problem, a constrained binary optimization problem. However, current quantum and quantum-inspired algorithms often require transforming these constrained problems into an unconstrained form, known as Quadratic Unconstrained Binary Optimization (QUBO). Such transformations can significantly impact the algorithms’ speed and efficiency. In this study, we evaluate five existing transformation methods and propose four novel approaches. We assess all nine methods using Simulated Annealing and find that three of our approaches outperform existing methods in terms of execution time and the quality and quantity of feasible solutions found. Additionally, we tested these transformations on quantum annealers, which were unable to solve even small problem instances, due to limitations in connectivity and error rates. However, our results highlight the advantages of the new approaches, which reduce the total number of variables in the QUBO representation. This is a critical factor for enhanced performance on emerging quantum hardware, since it also reduces the required number of qubits and the embedding chain lengths.
Recent advancements in quantum computing have demonstrated significant potential for solving combinatorial optimization problems, like the quadratic knapsack problem, a constrained binary optimization problem. How- ever, current quantum and quantum-inspired algorithms often require transforming these constrained problems into an unconstrained form, known as Quadratic Unconstrained Binary Optimization (QUBO). Such transfor- mations can significantly impact the algorithms’ speed and efficiency. In this study, we evaluate five existing transformation methods and propose four novel approaches. We assess all nine methods using Simulated An- nealing and find that three of our approaches outperform existing methods in terms of execution time and the quality and quantity of feasible solutions found. Additionally, we tested these transformations on quantum annealers, which were unable to solve even small problem instances, due to limitations in connectivity and error rates. However, our results highlight the advantages of the new approaches, which reduce the total num- ber of variables in the QUBO representation. This is a critical factor for enhanced performance on emerging quantum hardware, since it also reduces the required number of qubits and the embedding chain lengths.
Polar decoders such as successive-cancellation and successive-cancellation list decoders are limited by their sequential nature, which leads to a linear increase in latency with the codeword length. Heuristic based decoders such as quantum annealing have been proposed to overcome this limitation. However, these decoders have shown poor performance when decoding polar codes with more than eight bits. In this paper, we developed new meta-heuristic based polar decoder, called xSA, which uses a new receiver constraint modeled by the binary cross-entropy function. We also propose a method to determine the weights used in a quadratic unconstrained binary optimization (QUBO) function. The polar code is assumed to have been sent across an AWGN channel and we conducted our experiments and simulations using PyQUBO and dwave-neal. Our results show that xSA is able to decode codes of length 16 and 32 with a near-ML FER performance, presenting itself as a promising alternative to traditional polar decoders for real world applications and next generation cellular communications.
Practical discrete optimization problems often contain multidimensional arrays of variables with linear constraints, which complicates their conversion to QUBO (quadratic unconstrained binary optimization) form. The article proposes a systematic approach to transforming such problems, which includes three key steps: the transition from a multidimensional representation of variables to a one-dimensional one using the Kronecker product of matrices, the reduction of mixed variables to binary ones, and the introduction of linear constraints into the objective function through quadratic penalties. Explicit computational formulas are obtained for each stage, simplifying their software implementation. The developed method is illustrated with examples from graph theory and combinatorial optimization, including classical formulations, confirming its universality. The results of the article allow standardizing the process of adapting problems for solving on quantum annealing algorithms (e.g., D-Wave) and classical QUBO solvers.