The original online version of this article (Abdirahman Alasow, Marek Perkowski (2023) Quantum Algorithm for Mining Frequent Patterns for Association Rule Mining. Journal of Quantum Information Science, 13, 1-23. http...The original online version of this article (Abdirahman Alasow, Marek Perkowski (2023) Quantum Algorithm for Mining Frequent Patterns for Association Rule Mining. Journal of Quantum Information Science, 13, 1-23. https://doi.org/10.4236/jqis.2023.131001 unfortunately contains a mistake. The authors would like to clarify that Figure 11 and Figure 13 in our paper use a variant of diffusion quantum circuit that is not a standard Grover diffusion operator for the Boolean oracles and the phase oracles of L.K. Grover as presented in [1]-[3]. However, this variant of diffusion quantum circuit in those figures is the same as the quantum diffuser proposed by [4], which is the so-called “controlled-diffusion operator”.展开更多
Maximum frequent pattern generation from a large database of transactions and items for association rule mining is an important research topic in data mining. Association rule mining aims to discover interesting corre...Maximum frequent pattern generation from a large database of transactions and items for association rule mining is an important research topic in data mining. Association rule mining aims to discover interesting correlations, frequent patterns, associations, or causal structures between items hidden in a large database. By exploiting quantum computing, we propose an efficient quantum search algorithm design to discover the maximum frequent patterns. We modified Grover’s search algorithm so that a subspace of arbitrary symmetric states is used instead of the whole search space. We presented a novel quantum oracle design that employs a quantum counter to count the maximum frequent items and a quantum comparator to check with a minimum support threshold. The proposed derived algorithm increases the rate of the correct solutions since the search is only in a subspace. Furthermore, our algorithm significantly scales and optimizes the required number of qubits in design, which directly reflected positively on the performance. Our proposed design can accommodate more transactions and items and still have a good performance with a small number of qubits.展开更多
In this paper,we do research on generating unitary matrices for quantum circuits automatically.We consider that quantum circuits are divided into six types,and the unitary operator expressions for each type are offere...In this paper,we do research on generating unitary matrices for quantum circuits automatically.We consider that quantum circuits are divided into six types,and the unitary operator expressions for each type are offered.Based on this,we propose an algorithm for computing the circuit unitary matrices in detail.Then,for quantum logic circuits composed of quantum logic gates,a faster method to compute unitary matrices of quantum circuits with truth table is introduced as a supplement.Finally,we apply the proposed algorithm to different reversible benchmark circuits based on NCT library(including NOT gate,Controlled-NOT gate,Toffoli gate)and generalized Toffoli(GT)library and provide our experimental results.展开更多
Search-based statistical structural testing(SBSST)is a promising technique that uses automated search to construct input distributions for statistical structural testing.It has been proved that a simple search algorit...Search-based statistical structural testing(SBSST)is a promising technique that uses automated search to construct input distributions for statistical structural testing.It has been proved that a simple search algorithm,for example,the hill-climber is able to optimize an input distribution.However,due to the noisy fitness estimation of the minimum triggering probability among all cover elements(Tri-Low-Bound),the existing approach does not show a satisfactory efficiency.Constructing input distributions to satisfy the Tri-Low-Bound criterion requires an extensive computation time.Tri-Low-Bound is considered a strong criterion,and it is demonstrated to sustain a high fault-detecting ability.This article tries to answer the following question:if we use a relaxed constraint that significantly reduces the time consumption on search,can the optimized input distribution still be effective in faultdetecting ability?In this article,we propose a type of criterion called fairnessenhanced-sum-of-triggering-probability(p-L1-Max).The criterion utilizes the sum of triggering probabilities as the fitness value and leverages a parameter p to adjust the uniformness of test data generation.We conducted extensive experiments to compare the computation time and the fault-detecting ability between the two criteria.The result shows that the 1.0-L1-Max criterion has the highest efficiency,and it is more practical to use than the Tri-Low-Bound criterion.To measure a criterion’s fault-detecting ability,we introduce a definition of expected faults found in the effective test set size region.To measure the effective test set size region,we present a theoretical analysis of the expected faults found with respect to various test set sizes and use the uniform distribution as a baseline to derive the effective test set size region’s definition.展开更多
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 Electro...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 Grover-based 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.展开更多
In this paper, classical and continuous variable (CV) quantum neural network hybrid multi-classifiers are presented using the MNIST dataset. Currently available classifiers can classify only up to two classes. The pro...In this paper, classical and continuous variable (CV) quantum neural network hybrid multi-classifiers are presented using the MNIST dataset. Currently available classifiers can classify only up to two classes. The proposed architecture allows networks to classify classes up to n<sup>m</sup> classes, where n represents cutoff dimension and m the number of qumodes on photonic quantum computers. The combination of cutoff dimension and probability measurement method in the CV model allows a quantum circuit to produce output vectors of size n<sup>m</sup>. They are then interpreted as one-hot encoded labels, padded with n<sup>m</sup> - 10 zeros. The total of seven different classifiers is built using 2, 3, …, 6, and 8-qumodes on photonic quantum computing simulators, based on the binary classifier architecture proposed in “Continuous variable quantum neural networks” [1]. They are composed of a classical feed-forward neural network, a quantum data encoding circuit, and a CV quantum neural network circuit. On a truncated MNIST dataset of 600 samples, a 4-qumode hybrid classifier achieves 100% training accuracy.展开更多
We present a new approach to the synthesis of quantum automata. In previous research, reversible quantum automata were designed from tabular specifications or state graphs, and minimum length codes, which lead to circ...We present a new approach to the synthesis of quantum automata. In previous research, reversible quantum automata were designed from tabular specifications or state graphs, and minimum length codes, which lead to circuits with Toffoli gates with high numbers of inputs and thus to high quantum costs. This paper is the first to present a method to synthesize Sequential Quantum Circuits directly from flowcharts. In this paper, we directly map flowcharts to reversible/quantum circuits, using only inverters, 2*2 Feynman gates and 3*3 Toffoli gates, and thus reducing quantum costs. Our method has been confirmed by experiments on several benchmarks of practical flowcharts.展开更多
文摘The original online version of this article (Abdirahman Alasow, Marek Perkowski (2023) Quantum Algorithm for Mining Frequent Patterns for Association Rule Mining. Journal of Quantum Information Science, 13, 1-23. https://doi.org/10.4236/jqis.2023.131001 unfortunately contains a mistake. The authors would like to clarify that Figure 11 and Figure 13 in our paper use a variant of diffusion quantum circuit that is not a standard Grover diffusion operator for the Boolean oracles and the phase oracles of L.K. Grover as presented in [1]-[3]. However, this variant of diffusion quantum circuit in those figures is the same as the quantum diffuser proposed by [4], which is the so-called “controlled-diffusion operator”.
文摘Maximum frequent pattern generation from a large database of transactions and items for association rule mining is an important research topic in data mining. Association rule mining aims to discover interesting correlations, frequent patterns, associations, or causal structures between items hidden in a large database. By exploiting quantum computing, we propose an efficient quantum search algorithm design to discover the maximum frequent patterns. We modified Grover’s search algorithm so that a subspace of arbitrary symmetric states is used instead of the whole search space. We presented a novel quantum oracle design that employs a quantum counter to count the maximum frequent items and a quantum comparator to check with a minimum support threshold. The proposed derived algorithm increases the rate of the correct solutions since the search is only in a subspace. Furthermore, our algorithm significantly scales and optimizes the required number of qubits in design, which directly reflected positively on the performance. Our proposed design can accommodate more transactions and items and still have a good performance with a small number of qubits.
基金This work was funded by the Natural Science Foundation of Jiangsu Province(Grant No:BK20171458)the Yangzhou University International Academic Exchange Fund.
文摘In this paper,we do research on generating unitary matrices for quantum circuits automatically.We consider that quantum circuits are divided into six types,and the unitary operator expressions for each type are offered.Based on this,we propose an algorithm for computing the circuit unitary matrices in detail.Then,for quantum logic circuits composed of quantum logic gates,a faster method to compute unitary matrices of quantum circuits with truth table is introduced as a supplement.Finally,we apply the proposed algorithm to different reversible benchmark circuits based on NCT library(including NOT gate,Controlled-NOT gate,Toffoli gate)and generalized Toffoli(GT)library and provide our experimental results.
基金Publication of this article in an open access journal was funded by the Portland State University Library’s Open Access Fund.
文摘Search-based statistical structural testing(SBSST)is a promising technique that uses automated search to construct input distributions for statistical structural testing.It has been proved that a simple search algorithm,for example,the hill-climber is able to optimize an input distribution.However,due to the noisy fitness estimation of the minimum triggering probability among all cover elements(Tri-Low-Bound),the existing approach does not show a satisfactory efficiency.Constructing input distributions to satisfy the Tri-Low-Bound criterion requires an extensive computation time.Tri-Low-Bound is considered a strong criterion,and it is demonstrated to sustain a high fault-detecting ability.This article tries to answer the following question:if we use a relaxed constraint that significantly reduces the time consumption on search,can the optimized input distribution still be effective in faultdetecting ability?In this article,we propose a type of criterion called fairnessenhanced-sum-of-triggering-probability(p-L1-Max).The criterion utilizes the sum of triggering probabilities as the fitness value and leverages a parameter p to adjust the uniformness of test data generation.We conducted extensive experiments to compare the computation time and the fault-detecting ability between the two criteria.The result shows that the 1.0-L1-Max criterion has the highest efficiency,and it is more practical to use than the Tri-Low-Bound criterion.To measure a criterion’s fault-detecting ability,we introduce a definition of expected faults found in the effective test set size region.To measure the effective test set size region,we present a theoretical analysis of the expected faults found with respect to various test set sizes and use the uniform distribution as a baseline to derive the effective test set size region’s definition.
文摘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 Grover-based 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.
文摘In this paper, classical and continuous variable (CV) quantum neural network hybrid multi-classifiers are presented using the MNIST dataset. Currently available classifiers can classify only up to two classes. The proposed architecture allows networks to classify classes up to n<sup>m</sup> classes, where n represents cutoff dimension and m the number of qumodes on photonic quantum computers. The combination of cutoff dimension and probability measurement method in the CV model allows a quantum circuit to produce output vectors of size n<sup>m</sup>. They are then interpreted as one-hot encoded labels, padded with n<sup>m</sup> - 10 zeros. The total of seven different classifiers is built using 2, 3, …, 6, and 8-qumodes on photonic quantum computing simulators, based on the binary classifier architecture proposed in “Continuous variable quantum neural networks” [1]. They are composed of a classical feed-forward neural network, a quantum data encoding circuit, and a CV quantum neural network circuit. On a truncated MNIST dataset of 600 samples, a 4-qumode hybrid classifier achieves 100% training accuracy.
文摘We present a new approach to the synthesis of quantum automata. In previous research, reversible quantum automata were designed from tabular specifications or state graphs, and minimum length codes, which lead to circuits with Toffoli gates with high numbers of inputs and thus to high quantum costs. This paper is the first to present a method to synthesize Sequential Quantum Circuits directly from flowcharts. In this paper, we directly map flowcharts to reversible/quantum circuits, using only inverters, 2*2 Feynman gates and 3*3 Toffoli gates, and thus reducing quantum costs. Our method has been confirmed by experiments on several benchmarks of practical flowcharts.
