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

A Method for Optimizing q-Valued Quantum Multiplexers

Justin Morgan

Published May 25, 2017• 0 citations
Publisher

Abstract

This paper presents a new approach to optimize arbitrary quantum circuits based on multi-valued Quantum Multiplexers. We define standard, and fixed polarity forms for binary valued quantum multiplexers that are analogous to the disjoint sum of product and Fixed Polarity Reed-Muller Forms for classical logic functions. Then, the method is extended to logic with an arbitrary radix. The algorithm produced requires O(mqm) butterfly transformations, where m is the number of control variables, and q is the radix of logic. A software script is then added and described to facilitate in the computation of larger and more complex quantum multiplexers.

DOI
10.15760/honors.480

Related papers

A Reed Muller-based approach for optimization of general binary quantum multiplexers

Kevin Jin, Tahsin Saffat, Marek A. Perkowski

Previous work has provided methods for decomposing unitary matrices to series of quantum multiplexers, but the multiplexers created in this way are highly non-minimal. This paper presents a new approach for optimizing quantum multiplexers with arbitrary single-qubit quantum target functions. For quantum multiplexers, we define standard forms and two types of new forms: fixed polarity quantum forms (FPQF) and Kronecker quantum forms (KQF), which are analogous to Minterm Sum of Products forms, Fixed Polarity Reed-Muller (FPRM) forms, and Kronecker Reed-Muller (KRM) forms, respectively, for classical logic functions. Drawing inspiration from the usage of butterfly diagrams for FPRM and KRM forms, we devise a method to exhaustively construct all FPQF and KQF forms. Thus, the new forms can be used to optimize quantum circuits with arbitrary target unitary matrices, rather than only multi-controlled NOT gates such as CNOT, CCNOT, and their extensions. Experimental results on FPQF and KQF forms, as well as FPRM and KRM classical forms, applied to various target gates such as NOT, V, V+, Hadamard, and Pauli rotations, demonstrate that FPQF and KQF forms greatly reduce the gate cost of quantum multiplexers in both randomly generated data and FPRM benchmarks.

arXiv:1902.06229•Feb 17, 2019•0 citations

Minimization of AND-XOR Expressions with Decoders for Quantum Circuits

Sonia Yang, Ali Al-Bayaty, Marek Perkowski

This paper introduces a new logic structure for reversible quantum circuit synthesis. Our synthesis method aims to minimize the quantum cost of reversible quantum circuits with decoders. In this method, multi-valued input, binary output (MVI) functions are utilized as a mathematical concept only, but the circuits are binary. We introduce the new concept of ``Multi-Valued Input Fixed Polarity Reed-Muller (MVI-RM)" forms. Our decoder-based circuit uses three logical levels in contrast to commonly-used methods based on Exclusive-or Sum of Products (ESOP) with two levels (AND-XOR expressions), realized by Toffoli gates. In general, the high number of input qubits in the resulting Toffoli gates is a problem that greatly impacts the quantum cost. Using decoders decreases the number of input qubits in these Toffoli gates. We present two practical algorithms for three-level circuit synthesis by finding the MVI-FPRM: products-matching and the newly developed butterfly diagrams. The best MVI-FPRM forms are factorized and reduced to approximate Multi-Valued Input Generalized Reed-Muller (MVI-GRM) forms.

quant-pharXiv:2601.02515•Jan 7, 2026•0 citations

A Polarity-Based Approach for Optimization of Multivalued Quantum Multiplexers with Arbitrary Single-Qubit Target Gates

Kevin Jin, Tahsin Saffat, Justin Morgan +1 more

Previous work has provided methods for decomposing unitary matrices to series of quantum multiplexers, but the multiplexer circuits created in this way may be highly non-minimal. This paper presents a new approach for optimizing quantum multiplexers with arbitrary single-qubit quantum target functions and ternary controls. For multivalued quantum multiplexers, we define standard forms and two types of new forms: Fixed Polarity Quantum Forms (FPQFs) and Kronecker Quantum Forms (KQFs). Drawing inspiration from the usage of butterfly diagrams, we devise a method to exhaustively construct new forms. In contrast to previous butterfly-based methods, which are used with classical Boolean functions, these new forms are used to optimize quantum circuits with arbitrary target unitary matrices. Experimental results on the new forms applied to various target gates such as NOT, V, V+, Hadamard, and Pauli rotations, demonstrate that these new forms greatly reduce the gate costs of ternary quantum multiplexers.

•Jan 1, 2020•2 citations

A Quantum Logic Circuit For Generating Fixed-Polarity Reed-Muller Coefficients

Mozammel H. A. Khan

Logic function representation using fixed-polarity Reed-Muller (FPRM) expression has manifold advantages over classical SOP expression. Moreover, FPRM expression is a very useful representation for logic function realization using quantum logic circuits. In this paper, we present a quantum logic circuit for generating FPRM coefficients for a given polarity vector from the truth vector of the function

International Conference on Electrical and Computer Engineering (ICECE)•Dec 1, 2006•0 citations

Gate Optimization of NEQR Quantum Circuits via PPRM Transformation

Shahab Iranmanesh, Hossein Aghababa, Kazim Fouladi

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.

arXiv:2409.14629•Sep 22, 2024•1 citation

Interpolating Binary and Multivalued Logical Quantum Gates

Zeno Toffano, François Dubois

A method for synthesizing quantum gates is presented based on interpolation methods applied to operators in Hilbert space. Starting from the diagonal forms of specific generating seed operators with non-degenerate eigenvalue spectrum one obtains for arity-one a complete family of logical operators corresponding to all the one-argument logical connectives. Scaling-up to n-arity gates is obtained by using the Kronecker product and unitary transformations. The quantum version of the Fourier transform of Boolean functions is presented and a Reed-Muller decomposition for quantum logical gates is derived. The common control gates can be easily obtained by considering the logical correspondence between the control logic operator and the binary logic operator. A new polynomial and exponential formulation of the Toffoli gate is presented. The method has parallels to quantum gate-T optimization methods using powers of multilinear operator polynomials. The method is then applied naturally to alphabets greater than two for multi-valued logical gates used for quantum Fourier transform, min-max decision circuits and multivalued adders.

International Electronic Conference on Entropy and Its Applications (ECEA)•Nov 20, 2017•4 citations
This paper presents a new approach to optimize arbitrary quantum circuits based on multi-valued Quantum Multiplexers. We define standard, and fixed polarity forms for binary valued quantum multiplexers that are analogous to the disjoint sum of product and Fixed Polarity Reed-Muller Forms for classical logic functions. Then, the method is extended to logic with an arbitrary radix. The algorithm produced requires O(mqm) butterfly transformations, where m is the number of control variables, and q is the radix of logic. A software script is then added and described to facilitate in the computation of larger and more complex quantum multiplexers.
Previous work has provided methods for decomposing unitary matrices to series of quantum multiplexers, but the multiplexers created in this way are highly non-minimal. This paper presents a new approach for optimizing quantum multiplexers with arbitrary single-qubit quantum target functions. For quantum multiplexers, we define standard forms and two types of new forms: fixed polarity quantum forms (FPQF) and Kronecker quantum forms (KQF), which are analogous to Minterm Sum of Products forms, Fixed Polarity Reed-Muller (FPRM) forms, and Kronecker Reed-Muller (KRM) forms, respectively, for classical logic functions. Drawing inspiration from the usage of butterfly diagrams for FPRM and KRM forms, we devise a method to exhaustively construct all FPQF and KQF forms. Thus, the new forms can be used to optimize quantum circuits with arbitrary target unitary matrices, rather than only multi-controlled NOT gates such as CNOT, CCNOT, and their extensions. Experimental results on FPQF and KQF forms, as well as FPRM and KRM classical forms, applied to various target gates such as NOT, V, V+, Hadamard, and Pauli rotations, demonstrate that FPQF and KQF forms greatly reduce the gate cost of quantum multiplexers in both randomly generated data and FPRM benchmarks.
This paper introduces a new logic structure for reversible quantum circuit synthesis. Our synthesis method aims to minimize the quantum cost of reversible quantum circuits with decoders. In this method, multi-valued input, binary output (MVI) functions are utilized as a mathematical concept only, but the circuits are binary. We introduce the new concept of ``Multi-Valued Input Fixed Polarity Reed-Muller (MVI-RM)" forms. Our decoder-based circuit uses three logical levels in contrast to commonly-used methods based on Exclusive-or Sum of Products (ESOP) with two levels (AND-XOR expressions), realized by Toffoli gates. In general, the high number of input qubits in the resulting Toffoli gates is a problem that greatly impacts the quantum cost. Using decoders decreases the number of input qubits in these Toffoli gates. We present two practical algorithms for three-level circuit synthesis by finding the MVI-FPRM: products-matching and the newly developed butterfly diagrams. The best MVI-FPRM forms are factorized and reduced to approximate Multi-Valued Input Generalized Reed-Muller (MVI-GRM) forms.
Previous work has provided methods for decomposing unitary matrices to series of quantum multiplexers, but the multiplexer circuits created in this way may be highly non-minimal. This paper presents a new approach for optimizing quantum multiplexers with arbitrary single-qubit quantum target functions and ternary controls. For multivalued quantum multiplexers, we define standard forms and two types of new forms: Fixed Polarity Quantum Forms (FPQFs) and Kronecker Quantum Forms (KQFs). Drawing inspiration from the usage of butterfly diagrams, we devise a method to exhaustively construct new forms. In contrast to previous butterfly-based methods, which are used with classical Boolean functions, these new forms are used to optimize quantum circuits with arbitrary target unitary matrices. Experimental results on the new forms applied to various target gates such as NOT, V, V+, Hadamard, and Pauli rotations, demonstrate that these new forms greatly reduce the gate costs of ternary quantum multiplexers.
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→∞m \rightarrow \inftym→∞), depending on the decomposition of multi-controlled NOT gates. Using nonlinear regression, the proposed transformation is estimated to reduce the exponential complexity from O(2m)O(2^m)O(2m) to O(1.5m)O(1.5^m)O(1.5m), 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.
A method for synthesizing quantum gates is presented based on interpolation methods applied to operators in Hilbert space. Starting from the diagonal forms of specific generating seed operators with non-degenerate eigenvalue spectrum one obtains for arity-one a complete family of logical operators corresponding to all the one-argument logical connectives. Scaling-up to n-arity gates is obtained by using the Kronecker product and unitary transformations. The quantum version of the Fourier transform of Boolean functions is presented and a Reed-Muller decomposition for quantum logical gates is derived. The common control gates can be easily obtained by considering the logical correspondence between the control logic operator and the binary logic operator. A new polynomial and exponential formulation of the Toffoli gate is presented. The method has parallels to quantum gate-T optimization methods using powers of multilinear operator polynomials. The method is then applied naturally to alphabets greater than two for multi-valued logical gates used for quantum Fourier transform, min-max decision circuits and multivalued adders.