Computers, Materials & Continua DOI:10.32604/cmc.2022.020483 

Article 
Novel Quantum Algorithms to Minimize Switching Functions Based on Graph Partitions
Department of Electrical and Computer Engineering, Portland State University, Portland, Oregon, 97201, USA
*Corresponding Author: Peng Gao. Email: Pengao@pdx.edu
Received: 26 May 2021; Accepted: 20 July 2021
Abstract: After Google reported its realization of quantum supremacy, Solving the classical problems with quantum computing is becoming a valuable research topic. Switching function minimization is an important problem in Electronic Design Automation (EDA) and logic synthesis, most of the solutions are based on heuristic algorithms with a classical computer, it is a good practice to solve this problem with a quantum processer. In this paper, we introduce a new hybrid classic quantum algorithm using Grover’s algorithm and symmetric functions to minimize small Disjoint Sum of Product (DSOP) and Sum of Product (SOP) for Boolean switching functions. Our method is based on graph partitions for arbitrary graphs to regular graphs, which can be solved by a Groverbased quantum searching algorithm we proposed. The Oracle for this quantum algorithm is built from Boolean symmetric functions and implemented with Lattice diagrams. It is shown analytically and verified by simulations on a quantum simulator that our methods can find all solutions to these problems.
Keywords: Boolean symmetric function; lattice diagrams; Grover’s searching algorithm
Grover’s Algorithm [1] is one of few most famous and most useful quantum algorithms to which many decision and optimization problems can be reduced. And Grover’s algorithm can provide quadratic speedup comparing to its classical counterpart [1]. Problems in Graph Theory are excellent candidates to be solved using Grover’s Algorithm. We present a uniform approach to use Grover’s Algorithm for solving several problems in Graph Theory which has multiple applications such as minimization of binary circuits [2].
Hypercube graphs [3] are an important category of graphs in Graph Theory because they have many interesting properties, such as bipartiteness, Hamiltonicity, and symmetry. These properties make hypercubes useful to solve problems in network topology [4], parallel computing [5], multivalued logic encoders/decoders [6], circuit switching modeling [7], and others.
Standard hypercubes are representations that are isomorphic to Karnaugh maps used in logic synthesis. Prime implicants of Boolean functions with n variables are subhypercubes or cliques with 2k nodes, k = 1,…, n. Hypercubes are generated by Cartesian products of binary vectors. Bettayeb introduced kary hypercubes [8] for computer networks. Here we introduce hybrid mixed hypercubes that are Cartesian products of arbitrary radix multivalued vectors. We name them generalized hypercubes. The generalized hypercube inherits all properties of hypercube but with a more general structure corresponding to switching functions with mixed variables. These are isomorphic to Marquand charts [9] known from minimization of multivalued switching circuits and Machine Learning.
Disjoint Sum of Products (DSOP) is one of commonly used form to minimize Boolean switching function. A DSOP realization of a Boolean function can be represented as a hypercube graph in which a realization with disjoint products of literals corresponds to disjoint partitioning to subhypercubes. This can be extended to Sum of Products (SOP) [10,11]. Unfortunately large size NPhard problems must be solved to find the exact solution. Often the methods require also to generate astronomic numbers of prime or product implicants.
Solving these problems with classical computers, even parallel computers, seems to not lead to interesting results and even not much has been published in recent years on these topics. However, future quantum computers give a promise. With the fast development of quantum circuits, several researchers focus on creating quantum algorithms for problems in Graph Theory [12]. Although now only small problems can be solved, future quantum computers will be able to achieve “quantum supremacy.” This gives promise to the work presented here that is not practical at the moment [13].
Our paper proposes new quantum algorithms to find disjoint partitions of arbitrary graphs to Eregular graphs. Eregular graph is a regular graph in which all vertices have the same degree [14,15]. These algorithms are based on Grover’s searching algorithm and use efficient ways to build Grover Oracle with Boolean symmetric functions. A hybrid algorithm is composed of a quantum algorithm and a standard algorithm. The classical part of the algorithm is executed on the classical computer which prepares data and controls for the quantum computer and receives partial results from it. With such a hybrid algorithm, we are able to distinguish special cases of Eregular graphs such as cycles, standard hypercubes and some generalized hypercubes. (Cycles are graphs in which every node has exactly two neighbor nodes. Eregular graph is composed of one or more cycles).
Two types of problems can be formulated for Eregular graph partition.
Problem 1. Full graph partitioning. Find all disjoint partitions of an arbitrary graph to Eregular subgraphs for given E, such that every node of the graph belongs to one of these regular subgraphs.
Problem 2. Partial graph partitioning. Find all disjoint partitions of an arbitrary graph to ERegular graphs for given E, such that every node belongs to one of these regular subgraphs or does not belong to any subgraph. We call this the partial partitioning.
Our hybrid quantum/classical algorithm in to solve the second type of problems can be applied to various some problems in minimizing switch circuit. The main innovative idea of our paper is to represent Graph Theory problems as collections of symmetric functions in which variables correspond to edges of the graph and nodes to certain constraints on them. Symmetric functions can be realized efficiently in multilevel circuits called lattices. Although our small examples below use for simplicity DSOP realizations of symmetric functions, it is important that for large functions the presented oracles should use optimized lattices [16].
The principle of the proposed methodology is to find some subsets of edges that satisfy various types of constraints related to symmetry. Many problems can be formulated as clustering, partitioning or covering with applications in logic synthesis and Machine Learning. Although we refer for details to our previous works [16,17], this paper is selfcontained and has a sufficient amount of information to follow main principles of our approach.
This paper is organized as follows. Section 2 presents Boolean Symmetric functions and their efficient realization in quantum circuits for Grover oracles. In Section 3 we present two quantum algorithms based on Grover. Section 4 only briefly outlines Grover’s Algorithm that is wellknown. those in which every node has at least one adjacent edge. Two problems are solved for Eregular graphs. Section 5 covers problems in Boolean Minimization.
Grover’s algorithm is another function block in our hybrid algorithm. It is a quantum searching algorithm invented by Grover in 1996, In our algorithm the constraints are formulated with symmetric function blocks and the Grover’s algorithm is used as a solver to find the solutions for different problems. For problems with single solution Grover’s algorithm finds an input variable vector with high probability to satisfy the blackbox Boolean function of the oracle, Fig. 1 is a diagram to present mainly function blocks of Grover’s searching algorithm. For problems with many solutions after finding the first solution, the oracle is modified by excluding this particular minterm (see explanation and example in [18]) and the Grover’s algorithm is run again. This is repeated until all solutions are found. A standard method used in applications in Grover’s algorithm where we want to find all solutions is to modify the oracle by exoring it with the products corresponding to the sets of solutions found. This reduces the space of remaining solutions (true minterms). This step is repeated until all found solutions are removed from the oracle. Details and oracle construction can be found in [19].
The input searching space of Grover’s algorithm is created by nqubits quantum registers with Hadamard gate, then those input data will pass to oracle function, at this stage, oracle will inverse the phase of solution item, next step is called amplitude amplification, the diffusion operator will increase the amplitude (probability) of target item, and decrease others. After
Oracle function in Grover’s algorithm should identify the target from input searching space, so it is problemspecific. There are many papers about Grover’s algorithm, but most of them do not pay attention to circuit complexity [20] and quantum cost [21] of oracles. Our approach can be characterized by an attempt to decrease the quantum cost of the oracle’s circuit. This paper follows the “engineering approach” to building quantum oracles where we create the oracle bottom up from simple blocks, possibly using ancilia qubits. This in contrast to several other authors that describe the oracle by a unitary matrix. Although their approach does not involve ancilia qubits it may lead to elementary gates that are not standard Toffoli, Feynman and NOT but arbitrary single qubit rotations and control rotations, which are very difficult or even impossible to realize in several practical existing quantum realization technologies.
3 Boolean Symmetric Functions and Lattice Diagrams for Oracles
In this section, the Boolean symmetric functions, Lattice diagrams are presented, the quantum layout of Lattice diagrams is shown in the end, this is the core part of symmetric blocks in our oracle.
Let f be a total Boolean function Bn → B, where B = {0, 1} and n > 1.
Definition 1. (Totally Symmetric Boolean Function) A Boolean function f is totally symmetric if its output is invariant under any permutation σ of its input bits:
Single index Symmetric Function S can be denoted as Sk, such that for every true minterm mi of S, the number of positive literals in all true minterms of this function is k, and the number of negative literals is n − k. For example a symmetric Boolean function
There exist several classical structures to realize Boolean symmetric functions [22]. The idea of Lattice Diagram [23] originates from Universal Akers Arrays (UAA) [24], which are well known for their areaefficiency and planar layout. Lattice Diagrams inherit this property from UAA but in several cases are even more efficient. First, comparing to UAA’s rectangular shape, Lattice Diagrams start from a tree expansion, then combining nonisomorphic nodes at the same level, thus making the shape of Lattice Diagram to be a triangle or trapezoid shape, and only keeping the minimum necessary size of repeated variables. Secondly, instead of assuming only Shannon expansions in UAA, Lattice Diagrams can use not only Shannon expansions but also positive and/or negative Davio expansions [25]. As we know quantum reversible circuits are based on EXOR rather OR operators, therefore EXORbased gates like Toffoli and Feynman are used [26,27], however, our paper is interested in those areas. This fact is important in quantum circuit synthesis, since Davio expansion can be mapped into Toffoli gate directly, which means Davio expansions lead to more efficient circuits than Shannon expansions which need two Toffoli gates. Lastly, Lattice Diagrams can handle multioutput functions, by changing the connection of nodes. This property makes Lattice diagram more powerful in synthesizing sets of symmetric functions. They are the base of our efficient oracles for large regular graphs. Their regularity and symmetry are good for 1dimensional or 2dimensional quantum layout [28], an issue very important from a practical realization point of view [29] of all types of circuit realization, but especially for quantum computing with respect to decoherence.
Fig. 2a in which signals flow from bottom to top presents a single output Lattice Diagram for function f(a, b, c); at the bottom there are small squares that can be filled with constants 0 or 1. For single output Lattice with n levels, we can realize every symmetric functions of n variables only by changing constants at the bottom level. Several functions of more than n variables and nonsymmetric function of n variables can be realized with nlevel Lattice. Fig. 2a is an example of 3level Lattice with a single output, the bottom level nodes correspond to constants and simple Boolean functions such as
3.2 Using Lattice Diagrams to Implement Symmetric Boolean Functions
3.2.1 Mapping Symmetric Functions to Davio Lattices
As we mentioned, Lattice Diagrams can use either Shannon or Davio expansions. If every cell in a Lattice Diagram has a uniform expansion, then we name that Lattice by the expansion. Thus Shannon Lattice has all cells being Shannon expansions. Expansion type is an important characterization of Lattice Diagram, there are three types of expansions: Shannon, Positive Davio, and Negative Davio.
Let
Positive Davio expansion [1,5] with respect to variable x1 is:
Negative Davio with respect to variable x1 is:
Fig. 4 is a singleoutput positive Davio Lattice.
The constants of the singleoutput lattice can be changed for different symmetric functions, more details and examples about constants and symmetric functions will be discussed in the next example. For multioutput lattices, the constants are determined by a specific symmetric function. This lattice has the capability to generate all symmetric functions by adding simple functions such as OR or EXOR on outputs. Given a Boolean function Q (a, b, c), it can be implemented by PDL layout from Fig. 4. The expansion function of each cell is a positive Davio gate. In this threelevel positive Davio lattice, output equation is:
We can find in this equation that every constant W, X, Y, Z is multiplied by a term that is a symmetric function. For example, a ⊕ b ⊕ c contains minterms:
In this matrix every row represents the “Davio cofactors” in Davio Lattice, every column represents symmetric functions from S0 to S3. For example, the row [0 1 0 1] means the related symmetric function of cofactor X is S1,3. Here we define the concept of Davio cofactor by analogy of the wellknown concept of Shannon cofactor. The equation of Q (a, b, c) in Fig. 4 is expressed with symmetric functions:
In Davio Lattice, each cofactor is associated with a group of symmetric indices, by selecting different order of cofactors we can get all symmetric function indices. For example, if we need function S1, we can set X and Z to 1, and remaining cofactors to 0. In Davio Lattice all terms are connected with XOR gate, so the equation Q (a, b, c) becomes 0
3.2.2 Mapping Davio Lattice into Quantum Reversible Circuit
Davio gate can be naturally mapped into a 3inputs Toffoli gate, as shown in Fig. 3b. Davio Lattice can be directly mapped into a quantum circuit. Fig. 6a shows a positive Davio Lattice of symmetric function S2(a, b, c). Since the symmetry vector contains only constants, this circuit can be simplified by constants propagation, as in Fig. 6b. More details in [16].
Fig. 6b is an example of gate level layout of the symmetric block used in our oracle, comparing with Fig. 6a, the optimized circuit in Fig. 6b cost fewer gates and ancilia wires, but even the circuit in Fig. 6a cost more resource, its cost is still better than mapping the simplified function to quantum circuit. Nowadays, the size of quantum circuit is still a limit for implementation of some quantum algorithm, the layout of Lattice Diagrams offers an efficient option to build our quantum oracles.
4 Oracle for Partitioning Generalized Hypercube
The ddimensional hypercube Qd is a graph whose node set consists of all binary vectors of length d, with two vertices being adjacent whenever the corresponding vectors differ at exactly one coordinate [31]. Hypercube is an important paradigm in parallel computing and network topology [32], each node has a permanent degree (dimension d).
Instead of the binary vector, generator of graphs can also use any multivalued vectors to create a new generalization of a hypercube graph, which we define here as a generalized hypercube.
Let us denote a clique with n nodes by Kn.
Definition 2. (Generalized Hypercube) [33]
The ncube or ndimensional generalized hypercube Qn is defined recursively in terms of Cartesian product of two graphs as follows:
The ncube also can be defined as a graph whose node set Vn consists of ndimensional vectors, where two adjacent vertices differ only in exactly one coordinate. Vectors could be any multivalued vectors. Classical hypercubes are built with binary vector K2 = {0, 1}. Hypercube in Fig. 7a is Q3 = K2
4.1 Disjoint Partitioning of Arbitrary Graphs to Regular Graphs
All our graph partitioning methods use the quantum Grover’s algorithm. With the benefit of Grover’s algorithm, quantum components of our algorithms gain a quadratic speed up comparing with the standard algorithm for these problems. Symmetric functions in Grover oracles are realized as in Section 2, but below a standard although less efficient realization is used for simplicity.
4.2 Example Oracles for the Hypercube Partitioning Problem
This first our oracle is designed for finding all disjoint partitions of an arbitrary undirected graph to regular graphs. In regular graphs, the degree of every node should be the same, we transform this condition into a Boolean equation and use this equation as a constraint to search all satisfied subsets of vertices in the graph. The ERegular graphs are found for every value of E separately.
Consider the graph G(V, E) in Fig. 8, V = {A, B, C, D, E, F}, E = {e1, e2, e3, e4, e5, e6, e7, e8, e9}. We want to find all complete partitionings to loops (closed path). Therefore every node has one incoming edge and one outcoming edge, which leads to node with 2symmetric function S2. We look for all partitions to cycles. Let ei where i ∈ [1, 9] be a Boolean variable corresponding to the edges. If edge ei belongs in a selected regular graph, then ei = 1; otherwise ei = 0. Thus the equations for nodes are as in Tab. 1.
In this example we got two solutions, one is (e1, e2, e4, e9, e8, e6) which is a cycle {A, B, C, E, F, D}, another solution is (e1, e2, e3, e7, e8, e9), this one is two ternary hypercubes (cycles) {A, B, C} and {D, E, F}. To find all complete partitionings we create an oracle that is using a logic AND of node functions for all nodes of the graph. If we want to calculate the solutions with the best costs we need to add a suboracle composed from the quantum counter and comparator and we need to repeat calling Grover with modified oracles.
In our oracle, besides the symmetric function blocks, we also use a quantum counter and comparator to save the quantum cost [34] of our circuit. In this example, we have 6 symmetric functions with related nodes. To check the satisfiability of our constraint, instead of using a 7
These results were simulated and verified by us using the Qiskit quantum simulator.
4.3 Partial Hypercube Partitioning
In partial hypercube partitioning, we find all subsets of nodes that are subhypercubes (cliques) but we allow also to exist nodes that do not belong to any subhypercube. Thus for graph from Fig. 8 all individual subgraphs {A, B, C}, {D, E, F}, {A, C, E}, {A, B, C, E}, and many other will be good solutions. The small modification of oracle is to allow the subsets of nodes, thus to every row of Tab. 1 we add to the node function of node FX additional function S0 of all its adjacent edges. For instance, now we have FC = e3e4̅e2 + e3̅e4e2 + ̅e3e4e2 + (̅e3 ̅e4 ̅e2).
By the property of Lattice structure, the symmetric block is a highly modular design in our algorithm, by adding a specific symmetric function, we can extend symmetric function of the block without generating a new Lattice diagram.
5 Solving DSOP SOP and Minimization Problems for Boolean Functions Using Partial Hypercube Partitioning
Partial Hypercube Partitioning is used to minimize Boolean functions. Normally, SOP minimization is reduced to finding the set of all prime implicants (primes) and next solving the setcovering problem to cover all true minterms with set of primes of the lowest cost. We follow the approach to find DSOP first. For instance in one variant our hybrid algorithm solves the DSOP minimization by finding partitions to large product implicants first and follows with partitions to smaller products. The result is not optimal but we obtain the quadratic speedup to a quantum component of this problem. DSOP can be transformed to SOP equations by enlarging each product implicant to the cheapest prime implicant. This is done by removing subsets of literals from these products, similar as it is done in [18], but this is not a subject of this paper.
DSOP minimization. All minterms included in a product implicant are pairwise compatible so the nodes of these minterms are all pairwise connected by edges in the graph (a clique, a subhypergraph). For instance, for a Boolean function specified by the set of minterms 0000, 0001, 0100, 0101, 0111, 0110, 1111, 1110 the minterms 0000, 0001, 0100, 0101 create a clique or a 3Regular subgraph that is disjoint from the other 3Regular subgraph 0111, 0110, 1111, 1110. This complete partition is a disjoint partition (clique covering) leading to a DSOP solution ̅ac + b c of this function. This is also an optimal SOP, as products ̅ac and bc are disjoint. In another DSOP variant the subgraph {0100, 0101, 0111, 0110} is found which corresponds to prime ̅ab to be next used in covering.
SOP minimization. Every product implicant from the DSOP found is individually extended to the largest prime for SOP using the method from [35]. In rare cases, but only in unspecified Boolean functions, minterms in a clique can be pairwise compatible but not compatible as a group thus they do not create a product implicant. In this case, a special transformation is done to create a SOP or a threelevel circuit is synthesized.
Example 1
Given is a Boolean function:
Since our quantum algorithm does not fetch data from the input Boolean function directly, we need to use a classical computer for preprocessing and postprocessing the data for the quantum Grover’s algorithm.
Step 1. Preprocessing (Classical Computer):
Based on the input function F(a, b, c, d), a compatibility graph is created by a classical computer, every true minterm in F(a, b, c, d) is a node in this graph, minterm
After the compatibility graph is created, the hypercube partition quantum algorithm is applied to find all disjoint implicants of F(a, b, c, d). In this case either the complete or the partial hypercube partition can be applied to solve this example, here we choose partial hypercube partition for illustration.
Step 2. Search for DSOP (Quantum Computer).
The indices of symmetric function used in our oracle are defined as (i, 0), where. The variable i is the degree of those nodes that are in majority in the compatibility graph. If the number is 0, i would be assigned to the degree of the second majority node. If there is more than one number of degree majority nodes such as in the example in Fig. 11, in which there is the same number of nodes of degree 1 and degree 4, the index i is chosen from either group of nodes. In this example symmetric indices (1, 0) are selected for demonstration. The second index ‘0’ in the constraint aims to identify the nodes and their connected edges which are not included in the result of the current searching procedure and keep them from being removed by the algorithm.
To find a better solution, both indices can be changed during the multiple calls of Grover’s algorithm. After the result is returned in the first searching, it would be saved in a classical computer, then the classical computer removes this solution from searching space by disabling the related edges at the input of the quantum algorithm. In the next round, the classical computer modifies the first index i in (i, 0), and runs our oracle with the reduced searching space. If no result is found, then index i is changed to the degree of the second majority node and step 2 is repeated until all edges are removed.
Step 3. Postprocessing (Classical Computer):
The results of each searching round are saved in the classical computer. When the whole searching process is finished, the DSOP/SOP of this function can be derived by performing a supercube calculation on sets of nodes, as explained below.
In Fig. 11, the initial run of Grover is done by setting the symmetric functions to S0,1 for all nodes. The result of this run is represented in a vector, like (1010000101), which means the edges e1, e3, e8, e10 are selected. With these edges, the classical computer traces back which nodes are selected. In this example the resulting sets of nodes are (n1, n2), (n3, n4), (n5, n6), (n7, n8). After transforming these pairs to the corresponding minterms, for pair (n1, n2) the minterms are
In the second run, because the degree of majority nodes is 3 (0 is illegal for index i), the indices are changed to (3, 0). Those edges: e2, e4, e5, e6, e7, e9 would be found by symmetric function S3,0, the related minterms are:
or DSOP:
Example 2
This example, to minimize function G(a, b, c, d) from Fig. 13a illustrates other properties of our method. Because the degree of the majority nodes is 3, the hybrid algorithm starts with symmetric function S0,3. Under this constraint, there are multiple solutions that can be found, the edges between nodes m1, m2, m4, m5 are selected as a possible solution for illustration. The result of the first search is
We developed a hybrid classical/quantum algorithm that uses the Grover’s algorithm in its quantum part. Various quantum oracles constructed here are all based on symmetric Boolean functions that can be efficiently realized in oracles. Our method is applied here to solve two types of hypercube graph partition problems and two types of Boolean function minimization problems. The SOP minimization problem finds multiple applications in classical logic synthesis and PLA (Programmable Logic Array), PAL (Programmable Array Logic), FPGA (FieldProgram Gate Array) design. The second, the DSOP minimization problem, is used in classical design as the first step of SOP minimization. DSOP minimization is also used as the first step of ESOP minimization. ESOP minimization is applied in classical logic for synthesis of arithmetic and testing circuits. More importantly ESOP logic is the fundament of minimizing arbitrary quantum functions realized with Inverter, Feynman, and multiqubit Toffoli gates. Grover’s algorithm gives quadratic speedup when compared to classical counterparts, thus giving promise to future minimization of large functions, also in Machine Learning.
The hybrid algorithm presented above illustrates how several abstract decision and optimization problems can be reduced to Graph Theory problems base on symmetric function. These problems include graph coloring, graph covering, maximum cliques, shortest path, longest path, Traveling Salesman, and domination. Similar methods can be applied to minimization of Exclusive Sum of Product (ESOP) and factorized ESOP expressions. In these problems the concept of compatibility of certain Boolean functions is fundamental and serves to define various partitioning problems to symmetric functions, such as those presented in Sections 1 to 5. Edges are created for pairs of compatible nodes. In addition please note that many interesting and practical problems can be also reduced to some of these Graph Theory problems. For instance, Sudoku Puzzle can be reduced to a graph coloring problem. We believe that there are other fascinating problems in Graph Theory and Topology that would get more efficient solutions with the power of quantum computing.
As far as we know there are no quantum algorithms yet for graph partitionings as defined here. There are also no classical algorithms for the problems formulated and solved in Section 3. There are no quantum algorithms that would solve classical DSOP and SOP minimization as presented in Section 5. These problems, like clique covering and similar, are all NPhard [36]. The presented methods will become practical with the appearance of quantum computers that can handle more qubits. The usefulness of these algorithms for NISQ (Noisy IntermediateScale Quantum) era computing [37] should be also studied.
Funding Statement: The authors received no specific funding for this study.
Conflicts of Interest: The authors declare that they have no conflicts of interest to report regarding the present study.
References
1. L. K. Grover, “A fast quantum mechanical algorithm for database search,” in Proc. 28th Annual ACM Symp. on Theory of Computing, USA, pp. 212–219, 1996.
2. M. J. Ciesielski, S. Yang and M. A. Perkowski, “Multiplevalued boolean minimization based on graph coloring,” in Proc. 1989 IEEE Int. Conf. of Computer Design, USA, pp. 265, 1989.
3. F. Harary, Graph Theory. Boston, MA, USA: AddisonWesley Publishing Company, 1969.
4. M. Schlosser, M. Sintek, S. Decker and W. Nejdl, “HyperCuP—hypercubes, ontologies, and efficient search on PeertoPeer networks,” Agents and PeertoPeer Computing, vol. 2530, pp. 112–124, 2003.
5. C. T. Chang, C. Y. Chang and J. P. Sheu, “BlueCube: Constructing a hypercube parallel computing and communication environment over bluetooth radio systems,” Journal of Parallel and Distributed Computing, vol. 66, no. 10, pp. 1243–1258, 2006.
6. K. O. Stanley, D. B. D’Ambrosio and J. Gauci, “A Hypercubebased encoding for evolving largescale neural networks,” Artificial Life, vol. 15, no. 2, pp. 185–212, 2009.
7. E. Chow, H. Madan, J. Peterson, D. Grunwald and D. Reed, “Hyperswitch network for the hypercube computer,” in Proc. of 15th Int. Symp. on Computer Architecture, USA, pp. 90–99, 1988.
8. S. Bettayeb, “On kary hypercube,” Theoretical Computer Science, vol. 140, no. 2, pp. 333–339, 1995.
9. A. Marquand, “On logical diagrams for n terms,” Philosophical Magazine, vol. 5, no. 12, pp. 266–270, 1881.
10. A. Mishchenko and M. A. Perkowski, “Fast heuristic minimization of exclusivesumsofproducts,” in Proceedings of ReedMuller’2001, Japan, pp. 213–215, 2001.
11. N. Song and M. A. Perkowski, “Minimization of exclusivesumofproducts expressions for multiplevalued input, incompletely specified functions,” IEEE Transactions on CAD, vol. 15, no. 4, pp. 385–395, 1996.
12. G. Frank and C. Lane, “Graph isomorphism and adiabatic quantum computing,” Physical Review. A, Atomic, Molecular, and Optical Physics, 201402, vol. 89, pp. 22342, 2014.
13. A. Frank, A. Kunal, B. Ryan, M. John, Z. Chen et al., “Quantum supremacy using a programmable superconducting processor,” Nature, vol. 574, no. 7779, pp. 505–510, 2019.
14. R. J. Trudeau, Introduction to Graph Theory, 2nd ed., New York: Dover Publications, 1994.
15. N. Biggs, Algebraic Graph Theory. Cambridge: Cambridge Univ. Press, 1974.
16. P. Gao, X. Song, Y. Li and M. A. Perkowski, “Realization of quantum oracles using symmetries of Boolean functions,” Quantum Information & Computation, vol. 20, no. 5&6, pp. 418–448, 2020.
17. M. J. Ciesielski, S. Yang and M. A. Perkowski, “Multiplevalued Boolean minimization based on graph coloring,” in Proceedings IEEE Int. Conf. on Computer Design, USA, pp. 265, 1989.
18. M. A. Perkowski, “Constraints satisfaction, reversible logic, invertible logic and Grover quantum oracles for practical problems,” in Proc. Reversible Computing 2020, Norway, pp. 3–32, 2020.
19. Y. Li, E. Tsai, M. A. Perkowski and X. Song, “Groverbased Ashenhurst–Curtis decomposition using quantum language quipper,” Quantum Information & Computation, vol. 19, no. 1&2, pp. 35–66, 2018.
20. A. Gilyén, S. Arunachalam and N. Wiebe, “Optimizing quantum optimization algorithms via faster quantum gradient computation,” in Proc. 13th ACMSIAM Symp. on Discrete Algorithms, CA, USA, pp. 1425–1444, 2002.
21. D. Maslov and G. W. Dueck, “Improved quantum cost for nbit Toffoli Gates,” Electronic Letter, vol. 39, no. 25, pp. 1790, 2003.
22. M. A. Perkowski, M. ChrzanowskaJeske and Y. Xu, “Lattice diagrams using Reed–Muller logic,” in Proc. of ReedMuller’97, U.K., pp. 85–102, 1997.
23. M. Lukac, D. Shah, M. A. Perkowski and M. Kameyama, “Synthesis of quantum arrays from Kronecker functional lattice diagrams,” IEICE Transaction on Information and System, vol. E97, no. 9, pp. 2262–2269, 2014.
24. S. B. Akers, “A rectangular logic array,” IEEE Transactions on Computer, vol. C21, no. 8, pp. 848–857, 1972.
25. T. Sasao and J. Butler, “A design method for lookup table type FPGA by pseudoKronecker expansion,” in Proc. on 24th Int. Symp. on MultipleValued Logic, Boston, USA, pp. 97–106, 1992.
26. R. Babbush, G. Craig, B. Dominic, W. Nathan, “Encoding electronic Spectra in quantum circuits with linear T complexity,” Physical Review, vol. 8, no. 4, pp. 041–015, 2018.
27. M. A. Perkowski, A. Mishchenko and M. ChrzanowskaJeske, “Generalized inclusive forms—new canonical Reed–Muller forms including minimum ESOPs,” VLSI Design, vol. 1, pp. 13–21, 2002.
28. A. Paler, L. M. Sasu, A. Florea and R. Andonie, “Machine learning optimization of quantum circuit layouts,” arxiv 2007.14608v1 [quantph], 29 July 2020.
29. M. A. Perkowski, M. Lukac, D. Shah and M. Kameyama, “Synthesis of quantum circuits in linear nearest neighbor model using positive Davio lattices,” Facta Universitatis, Electronic Energetics, vol. 24, no. 1, pp. 73–89, 2011.
30. V. P. Suprun and D. A. Gorodecky, “Matrix method of polynomial expansion of symmetric Boolean functions,” Automatic Control and Computer Sciences, vol. 47, no. 1, pp. 1–6, 2013.
31. W. H. Mills, “Some complete cycles on the nCube,” in Proc. of American Mathematical Society, MA, USA, pp. 640–643, 1963.
32. J. Zhou, Z.L. Wu, S.C. Yang and K.W. Yuan, “Symmetric property and reliability of balanced Hypercube,” IEEE Transactions on Computers, vol. 64, no. 3, pp. 876–881, 2015.
33. F. Harary, J. P. Hayes and H. J. Wu, “A survey of the theory of hypercube graphs,” Computers & Mathematics with Applications, vol. 15, no. 4, pp. 277–289, 1988.
34. D. Maslov and G. W. Dueck, “Improved quantum cost for nbit Toffoli gates,” Electronic Letter, vol. 39, no. 25, pp. 1790, 2003.
35. G. Yang, X. Song, H. William and M. A. Perkowski, “Fast synthesis of exact minimal reversible circuits using group theory,” in Proc. of the 2005 Asia and South Pacific Design Automation Conf., China, pp. 1002–1005, 2005.
36. Ch. Umans, T. Villa and A. SangiovanniVincentelli, “Complexity of twolevel logic minimization,” IEEE Transactions on CAD, vol. 25, pp. 1230–1246, 2006.
37. J. Preskill, “Quantum computing in the NISQ era and beyond,” Quantum, vol. 2, pp. 79, 2018.
This work is licensed under a Creative Commons Attribution 4.0 International License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. 