Source-linked AI summary
Gate Optimization of NEQR Quantum Circuits via PPRM Transformation
Shahab Iranmanesh, Hossein Aghababa, Kazim Fouladi
TL;DR
Quantum image representation faces runtime challenges as image sizes grow, while quantum systems have limited qubits. The paper transforms NEQR circuit ESOP expressions into PPRM form and reports reduced quantum cost across two gate decompositions.
Problem
Quantum image representation faces runtime challenges as image pixel counts grow, while current quantum systems have limited qubits and execution capacity.
Source: §1 · p. 1Method
Results
Average QC reductions were 105.5 times for NEQR circuits with MCNOT gates and 2.4 times for those with MCNOT-R gates, with average compression ratios of 99.05% and 58.91%, respectively.
Source: §5 · pp. 9–10Takeaways & Limitations
NEQR circuit optimization can be studied without compressing the image before its quantum representation.
Source: §1 · p. 2Karnaugh-map and similar methods are described as impractical and not guaranteed to produce globally optimal solutions.
Source: §2.3 · p. 5
Abstract
from arXiv · showhide
Quantum image representation (QIR) is a key challenge in quantum image processing (QIP) due to the large number of pixels in images, which increases the need for quantum gates and qubits. However, current quantum systems face limitations in run-time complexity and available qubits. This work aims to compress the quantum circuits of the Novel Enhanced Quantum Representation (NEQR) scheme by transforming their Exclusive-Or Sum-of-Products (ESOP) expressions into Positive Polarity Reed-Muller (PPRM) equivalents without adding ancillary qubits. Two cases of run-time complexity, exponential and linear, are considered for NEQR circuits with m controlling qubits ($m \rightarrow \infty$), depending on the decomposition of multi-controlled NOT gates. Using nonlinear regression, the proposed transformation is estimated to reduce the exponential complexity from $O(2^m)$ to $O(1.5^m)$, with a compression ratio approaching 100%. For linear complexity, the transformation is estimated to halve the run-time, with a compression ratio approaching 52%. Tests on six 256$\times$256 images show average reductions of 105.5 times for exponential cases and 2.4 times for linear cases, with average compression ratios of 99.05% and 58.91%, respectively.
1 Introduction
Quantum image representation faces runtime challenges as image pixel counts grow, while quantum systems have limited qubits and execution capacity. This work proposes transforming NEQR circuit expressions into PPRM form to reduce circuit cost without compressing images beforehand.
1 Introduction
- Quantum systems’ limited qubits, noise, and decoherence constrain circuit design and execution time, motivating gate-count and gate-type optimization.Source: §1 · p. 1
- QIR encodes digital images into quantum circuits, and increasing pixel counts in modern images and videos pose runtime challenges.NEQR is among the commonly used QIR models, alongside FRQI.Source: §1 · pp. 1–2
- Quantum image compression methods reduce QIR resources by compressing images before circuit construction, whereas this work targets NEQR circuits without prior image compression.Source: §1 · p. 2
- The work transforms ESOP expressions from NEQR circuits into PPRM expressions and evaluates quantum-cost and compression-rate growth as pixel counts increase.The authors estimate these rates using nonlinear regression.Source: §1 · p. 2
2 Background
NEQR encodes grayscale values and pixel coordinates in entangled qubit groups, but larger images require more control qubits and can raise circuit run-time complexity. PPRM expressions provide a canonical positive-polarity form for rewriting the ESOP expressions produced by NEQR circuits.
2.1 Multi-Controlled NOT (MCNOT) gate
- An MCNOT flips its target only when all control qubits are in state |1⟩; the paper considers a no-ancilla design and a reset design using two reusable ancillary qubits.Their quantum costs are 3 × 2^m − 4 and 19m − 32, respectively.Source: §2.1 · p. 3
- Applying multiple MCNOT gates to a target initialized to |0⟩ yields an ESOP: an XOR of product terms formed from the gates’ control states.The NEQR circuit’s output is mapped to ESOP expansions.Source: §2.1 · p. 4
2.2 NEQR
- NEQR represents grayscale values and pixel coordinates in two groups of entangled qubits, with controlled gates flipping grayscale bits for specified pixels.Larger images require more coordinate qubits and MCNOT gates with more controls, which can give circuits high run-time complexity.Source: §2.2 · p. 4
2.3 Positive Polarity Reed-Muller (PPRM) Expressions
- Manual simplification and methods such as Karnaugh maps are impractical for many inputs and do not guarantee a globally optimal solution.For a three-Toffoli example, the ESOP expression simplifies to YX ⊕ Y.Source: §2.3 · pp. 4–5
- PPRM is a positive-polarity form within the ESOP canonical families, whose conversion is expected to simplify NEQR circuit Boolean functions.Its product terms use positive, non-complemented literals.Source: §2.3 · p. 5
3 PPRM transform
The PPRM transform computes a Boolean function’s PPRM coefficients from its ESOP coefficients, then combines those coefficients with an input monomial vector to obtain the PPRM form. A blockwise XOR algorithm offers an alternative for computing the coefficients with less memory than the matrix method.
3 PPRM transform
- R(n) is formed by taking the n-times Kronecker product of R(1), and multiplying it by vector a yields the PPRM coefficient vector b.The vector a contains the coefficients of the original Boolean function’s ESOP expression.Source: §3 · p. 6
- The transform obtains the PPRM form by combining the monomial vector X(n) with coefficient vector b, using elementwise products and XOR.The coefficients b are computed by applying the same operation to R(n) and the ESOP coefficient vector a.Source: §3 · p. 6
- The blockwise algorithm repeatedly XORs corresponding odd and even blocks, stores results in even blocks, and doubles the block size at each iteration.It computes b in dimension 2^n faster and with considerably less memory than using R(n).Source: §3 · p. 6
4 Simulation Results and Analysis
The PPRM transformation was tested on six 256 × 256 images and on random grayscale images of increasing sizes. The experiments report QC reductions for MCNOT and MCNOT-R circuits, alongside estimated optimization and compression trends as the number of controlling qubits increases.
4 Simulation Results and Analysis
- Each of six 256 × 256 images was represented as a 65536×8 binary matrix, with rows for pixels and columns for grayscale-qubit product-term coefficients.Each column was transformed into a vector and combined with X(n) to obtain PPRM expressions used to control new MCNOT gates.Source: §4 · p. 7
- Random-image simulations covered sizes from 21 × 21 to 211 × 211 and controlling-qubit counts from 2 to 22; larger images could not be simulated on the stated hardware.The simulations used an Intel Core i3-6100 × 4 CPU, 8 GB RAM, and Linux Ubuntu 24.04.1 LTS.Source: §4 · p. 7
- Average QC reductions were 105.5-fold with MCNOT and 2.4-fold with MCNOT-R, with average compression ratios of 99.05% and 58.91%, respectively.Tables 1 and 2 report the per-image reductions and compression ratios for the six tested images.Source: §4 · p. 7, Table 1 · p. 8, Table 2 · p. 8
- For random images, estimated compression ratios approach 100% with MCNOT and 52% with MCNOT-R as the number of controlling qubits increases.The optimization rate for MCNOT-R is estimated to approach 2.10.Source: §4 · p. 8
5 Conclusion
PPRM transformation reduced the quantum cost of NEQR circuits across six 256 × 256 images, with outcomes differing by MCNOT gate type. Tests on random-valued images also indicate distinct scaling trends for exponential- and linear-cost circuits.
5 Conclusion
- 105.5 times for MCNOT circuits and 2.4 times for MCNOT-R circuits were the average QC reductions across six 256 × 256 images, with compression ratios of 99.05% and 58.91%, respectively.The ratios correspond to the gate types in the same order.Source: §5 · pp. 9–10
- For NEQR circuits with exponential QC O(2^m), optimization rate increases exponentially with controlling-qubit count m, estimated by O(1.33^m); compression ratios approach 100% for MCNOT and 52% for MCNOT-R circuits.The analysis used random-valued images with dimensions ranging from 21 × 21 to 211 × 211.Source: §5 · p. 10
- For NEQR circuits with linear QC O(m), the optimization rate depends on controlling-qubit count, decreases as m increases, and approaches a constant value of 2.1; MCNOT-R compression ratios tend toward 52%.Random-valued images with dimensions from 21×21 to 211×211 were analyzed.Source: §5 · p. 10