Shenggen Zheng

Yonghe Zhang, Liwei Ni, Jiaxi Zhang et al. · pku

NPN classification has many applications in the synthesis and verification of digital circuits. The canonical-form-based method is the most common approach, designing a canonical form as representative for the NPN equivalence class first and then computing the transformation function according to the canonical form. Most works use variable symmetries and several signatures, mainly based on the cofactor, to simplify the canonical form construction and computation. This paper describes a novel canonical form and its computation algorithm by introducing Boolean influence to NPN classification, which is a basic concept in analysis of Boolean functions. We show that influence is input-negation-independent, input-permutation-dependent, and has other structural information than previous signatures for NPN classification. Therefore, it is a significant ingredient in speeding up NPN classification. Experimental results prove that influence plays an important role in reducing the transformation enumeration in computing the canonical form. Compared with the state-of-the-art algorithm implemented in ABC, our influence-aided canonical form for exact NPN classification gains up to 5.5x speedup.

Liwei Ni, Jiaxi Zhang, Shenggen Zheng et al.

Boolean equivalence allows Boolean networks with identical functionality to exhibit diverse graph structures. This gives more room for exploration in logic optimization, while also posing a challenge for tasks involving consistency between Boolean networks. To tackle this challenge, we introduce BoolSkeleton, a novel Boolean network skeletonization method that improves the consistency and reliability of design-specific evaluations. BoolSkeleton comprises two key steps: preprocessing and reduction. In preprocessing, the Boolean network is transformed into a defined Boolean dependency graph, where nodes are assigned the functionality-related status. Next, the homogeneous and heterogeneous patterns are defined for the node-level pattern reduction step. Heterogeneous patterns are preserved to maintain critical functionality-related dependencies, while homogeneous patterns can be reduced. Parameter K of the pattern further constrains the fanin size of these patterns, enabling fine-tuned control over the granularity of graph reduction. To validate BoolSkeleton's effectiveness, we conducted four analysis/downstream tasks around the Boolean network: compression analysis, classification, critical path analysis, and timing prediction, demonstrating its robustness across diverse scenarios. Furthermore, it improves above 55% in the average accuracy compared to the original Boolean network for the timing prediction task. These experiments underscore the potential of BoolSkeleton to enhance design consistency in logic synthesis.

Jiaxi Zhang, Liwei Ni, Shenggen Zheng et al.

Boolean matching is significant to digital integrated circuits design. An exhaustive method for Boolean matching is computationally expensive even for functions with only a few variables, because the time complexity of such an algorithm for an n-variable Boolean function is $O(2^{n+1}n!)$. Sensitivity is an important characteristic and a measure of the complexity of Boolean functions. It has been used in analysis of the complexity of algorithms in different fields. This measure could be regarded as a signature of Boolean functions and has great potential to help reduce the search space of Boolean matching. In this paper, we introduce Boolean sensitivity into Boolean matching and design several sensitivity-related signatures to enhance fast Boolean matching. First, we propose some new signatures that relate sensitivity to Boolean equivalence. Then, we prove that these signatures are prerequisites for Boolean matching, which we can use to reduce the search space of the matching problem. Besides, we develop a fast sensitivity calculation method to compute and compare these signatures of two Boolean functions. Compared with the traditional cofactor and symmetric detection methods, sensitivity is a series of signatures of another dimension. We also show that sensitivity can be easily integrated into traditional methods and distinguish the mismatched Boolean functions faster. To the best of our knowledge, this is the first work that introduces sensitivity to Boolean matching. The experimental results show that sensitivity-related signatures we proposed in this paper can reduce the search space to a very large extent, and perform up to 3x speedup over the state-of-the-art Boolean matching methods.

Amandeep Singh Bhatia, Shenggen Zheng

Recently, the use of mathematical methods and computer science applications have got significant response among biochemists and biologists to modeling the biological systems. The computational and mathematical methods have enormous potential for modeling the deoxyribonucleic acid (DNA) and ribonucleic acid (RNA) structures. The modeling of DNA and RNA secondary structures using automata theory had a significant impact in the fields of computer science. It is a natural goal to model the RNA secondary biomolecular structures using quantum computational models. Two-way quantum finite automata with classical states are more dominant than two-way probabilistic finite automata in language recognition. The main objective of this paper is on using two-way quantum finite automata with classical states to simulate, model and analyze the ribonucleic acid (RNA) sequences.

Amandeep Singh Bhatia, Mandeep Kaur Saggi, Shenggen Zheng et al.

Motivated by particle swarm optimization (PSO) and quantum computing theory, we have presented a quantum variant of PSO (QPSO) mutated with Cauchy operator and natural selection mechanism (QPSO-CD) from evolutionary computations. The performance of proposed hybrid quantum-behaved particle swarm optimization with Cauchy distribution (QPSO-CD) is investigated and compared with its counterparts based on a set of benchmark problems. Moreover, QPSO-CD is employed in well-studied constrained engineering problems to investigate its applicability. Further, the correctness and time complexity of QPSO-CD are analysed and compared with the classical PSO. It has been proven that QPSO-CD handles such real-life problems efficiently and can attain superior solutions in most of the problems. The experimental results showed that QPSO associated with Cauchy distribution and natural selection strategy outperforms other variants in the context of stability and convergence.

Shenggen Zheng, Daowen Qiu, Jozef Gruska

In this paper we explore the power of AM for the case that verifiers are {\em two-way finite automata with quantum and classical states} (2QCFA)--introduced by Ambainis and Watrous in 2002--and the communications are classical. It is of interest to consider AM with such "semi-quantum" verifiers because they use only limited quantum resources. Our main result is that such Quantum Arthur-Merlin proof systems (QAM(2QCFA)) with polynomial expected running time are more powerful than in the case verifiers are two-way probabilistic finite automata (AM(2PFA)) with polynomial expected running time. Moreover, we prove that there is a language which can be recognized by an exponential expected running time QAM(2QCFA), but can not be recognized by any AM(2PFA), and that the NP-complete language $L_{knapsack}$ can also be recognized by a QAM(2QCFA) working only on quantum pure states using unitary operators.