In the rapidly evolving domain of quantum computing,Shor’s algorithm has emerged as a groundbreaking innovation with far-reaching implications for the field of cryptographic security.However,the efficacy of Shor’s a...In the rapidly evolving domain of quantum computing,Shor’s algorithm has emerged as a groundbreaking innovation with far-reaching implications for the field of cryptographic security.However,the efficacy of Shor’s algorithm hinges on the critical step of determining the period,a process that poses a substantial computational challenge.This article explores innovative quantum optimization solutions that aim to enhance the efficiency of Shor’s period finding algorithm.The article focuses on quantum development environments,such as Qiskit and Cirq.A detailed analysis is conducted on three notable tools:Qiskit Transpiler,BQSKit,and Mitiq.The performance of these tools is evaluated in terms of execution time,precision,resource utilization,the number of quantum gates,circuit synthesis optimization,error mitigation,and qubit fidelity.Through rigorous case studies,we highlight the strengths and limitations of these tools,shedding light on their potential impact on integer factorization and cybersecurity.Our findings underscore the importance of quantum optimization and lay the foundation for future developments in quantum algorithmic enhancements,particularly within the Qiskit and Cirq quantum development environments.展开更多
Shor proposed a polynomial time algorithm for computing the order of one element in a multiplicative group using a quantum computer. Based on Miller’s randomization, he then gave a factorization algorithm. But the al...Shor proposed a polynomial time algorithm for computing the order of one element in a multiplicative group using a quantum computer. Based on Miller’s randomization, he then gave a factorization algorithm. But the algorithm has two shortcomings, the order must be even and the output might be a trivial factor. Actually, these drawbacks can be overcome if the number is an RSA modulus. Applying the special structure of the RSA modulus, an algorithm is presented to overcome the two shortcomings. The new algorithm improves Shor’s algorithm for factoring RSA modulus. The cost of the factorization algorithm almost depends on the calculation of the order of 2 in the multiplication group.展开更多
Many classical encoding algorithms of vector quantization （VQ） of image compression that can obtain global optimal solution have computational complexity O（N）. A pure quantum VQ encoding algorithm with probability...Many classical encoding algorithms of vector quantization （VQ） of image compression that can obtain global optimal solution have computational complexity O（N）. A pure quantum VQ encoding algorithm with probability of success near 100% has been proposed, that performs operations 45√N times approximately. In this paper, a hybrid quantum VQ encoding algorithm between the classical method and the quantum algorithm is presented. The number of its operations is less than √N for most images, and it is more efficient than the pure quantum algorithm.展开更多
Vector quantization （VQ） is an important data compression method. The key of the encoding of VQ is to find the closest vector among N vectors for a feature vector. Many classical linear search algorithms take O（N）...Vector quantization （VQ） is an important data compression method. The key of the encoding of VQ is to find the closest vector among N vectors for a feature vector. Many classical linear search algorithms take O（N） steps of distance computing between two vectors. The quantum VQ iteration and corresponding quantum VQ encoding algorithm that takes O（√N） steps are presented in this paper. The unitary operation of distance computing can be performed on a number of vectors simultaneously because the quantum state exists in a superposition of states. The quantum VQ iteration comprises three oracles, by contrast many quantum algorithms have only one oracle, such as Shor＇s factorization algorithm and Grover＇s algorithm. Entanglement state is generated and used, by contrast the state in Grover＇s algorithm is not an entanglement state. The quantum VQ iteration is a rotation over subspace, by contrast the Grover iteration is a rotation over global space. The quantum VQ iteration extends the Grover iteration to the more complex search that requires more oracles. The method of the quantum VQ iteration is universal.展开更多
The advent of Grover’s algorithm presents a significant threat to classical block cipher security,spurring research into post-quantum secure cipher design.This study engineers quantum circuit implementations for thre...The advent of Grover’s algorithm presents a significant threat to classical block cipher security,spurring research into post-quantum secure cipher design.This study engineers quantum circuit implementations for three versions of the Ballet family block ciphers.The Ballet‑p/k includes a modular-addition operation uncommon in lightweight block ciphers.Quantum ripple-carry adder is implemented for both“32+32”and“64+64”scale to support this operation.Subsequently,qubits,quantum gates count,and quantum circuit depth of three versions of Ballet algorithm are systematically evaluated under quantum computing model,and key recovery attack circuits are constructed based on Grover’s algorithm against each version.The comprehensive analysis shows:Ballet-128/128 fails to NIST Level 1 security,while when the resource accounting is restricted to the Clifford gates and T gates set for the Ballet-128/256 and Ballet-256/256 quantum circuits,the design attains Level 3.展开更多
In order to improve the attack efficiency of the New FORK-256 function, an algorithm based on Grover's quantum search algorithm and birthday attack is proposed. In this algorithm, finding a collision for arbitrary...In order to improve the attack efficiency of the New FORK-256 function, an algorithm based on Grover's quantum search algorithm and birthday attack is proposed. In this algorithm, finding a collision for arbitrary hash function only needs O(2m/3) expected evaluations, where m is the size of hash space value. It is proved that the algorithm can obviously improve the attack efficiency for only needing O(2 74.7) expected evaluations, and this is more efficient than any known classical algorithm, and the consumed space of the algorithm equals the evaluation.展开更多
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.展开更多
It is widely believed that Shor＇s factoring algorithm provides a driving force to boost the quantum computing research.However, a serious obstacle to its binary implementation is the large number of quantum gates. No...It is widely believed that Shor＇s factoring algorithm provides a driving force to boost the quantum computing research.However, a serious obstacle to its binary implementation is the large number of quantum gates. Non-binary quantum computing is an efficient way to reduce the required number of elemental gates. Here, we propose optimization schemes for Shor＇s algorithm implementation and take a ternary version for factorizing 21 as an example. The optimized factorization is achieved by a two-qutrit quantum circuit, which consists of only two single qutrit gates and one ternary controlled-NOT gate. This two-qutrit quantum circuit is then encoded into the nine lower vibrational states of an ion trapped in a weakly anharmonic potential. Optimal control theory（OCT） is employed to derive the manipulation electric field for transferring the encoded states. The ternary Shor＇s algorithm can be implemented in one single step. Numerical simulation results show that the accuracy of the state transformations is about 0.9919.展开更多
When the Grover＇ s original algorithm is applied to search an unordered database, the success probability decreases rapidly with the increase of marked items. Aiming at this problem, a general quantum search algorith...When the Grover＇ s original algorithm is applied to search an unordered database, the success probability decreases rapidly with the increase of marked items. Aiming at this problem, a general quantum search algorithm with small phase rotations is proposed. Several quantum search algorithms can be derived from this algorithm according to different phase rotations. When the size of phase rotations are fixed at 0. 01π, the success probability of at least 99. 99% can be obtained in 0（√N/M） iterations.展开更多
The objective of this paper concerns at first the motivation and the method of Shor’s algorithm including remarks on quantum computing introducing an algorithmic description of the method.The corner stone of the Shor...The objective of this paper concerns at first the motivation and the method of Shor’s algorithm including remarks on quantum computing introducing an algorithmic description of the method.The corner stone of the Shor’s algorithm is the modular exponentiation that is themost computational component(in time and space).A linear depth unit based on phase estimation is introduced and a description of a generic version of a modular multiplier based on phases is introduced to build block of a gates to efficient modular exponentiation circuit.Our proposal includes numerical experiments achieved on both the IBM simulator using the Qiskit library and on quantum physical optimizers provided by IBM.The shor’s algorithm based on phase estimation succeeds in factoring integer numbers with more than 35 digits using circuits with about 100 qubits.展开更多
To overcome the difficulty of realizing large-scale quantum Fourier transform(QFT)within existing technology,this paper implements a resource-saving method(named t-bit semiclassical QFT over Z_(2n)),which could realiz...To overcome the difficulty of realizing large-scale quantum Fourier transform(QFT)within existing technology,this paper implements a resource-saving method(named t-bit semiclassical QFT over Z_(2n)),which could realize large-scale QFT using an arbitrary-scale quantum register.By developing a feasible method to realize the control quantum gate Rk,we experimentally realize the 2-bit semiclassical QFT over Z_(2-3)on IBM's quantum cloud computer,which shows the feasibility of the method.Then,we compare the actual performance of 2-bit semiclassical QFT with standard QFT in the experiments.The squared statistical overlap experimental data shows that the fidelity of 2-bit semiclassical QFT is higher than that of standard QFT,which is mainly due to fewer two-qubit gates in the semiclassical QFT.Furthermore,based on the proposed method,N=15 is successfully factorized by implementing Shor's algorithm.展开更多
An optimal estimator of quantum states based on a modified Kalman’s filter is proposed in this work. Such estimator acts after a state measurement, allowing us to obtain an optimal estimate of the quantum state resul...An optimal estimator of quantum states based on a modified Kalman’s filter is proposed in this work. Such estimator acts after a state measurement, allowing us to obtain an optimal estimate of the quantum state resulting in the output of any quantum algorithm. This method is much more accurate than other types of quantum measurements, such as, weak measurement, strong measurement, and quantum state tomography, among others.展开更多
文摘In the rapidly evolving domain of quantum computing,Shor’s algorithm has emerged as a groundbreaking innovation with far-reaching implications for the field of cryptographic security.However,the efficacy of Shor’s algorithm hinges on the critical step of determining the period,a process that poses a substantial computational challenge.This article explores innovative quantum optimization solutions that aim to enhance the efficiency of Shor’s period finding algorithm.The article focuses on quantum development environments,such as Qiskit and Cirq.A detailed analysis is conducted on three notable tools:Qiskit Transpiler,BQSKit,and Mitiq.The performance of these tools is evaluated in terms of execution time,precision,resource utilization,the number of quantum gates,circuit synthesis optimization,error mitigation,and qubit fidelity.Through rigorous case studies,we highlight the strengths and limitations of these tools,shedding light on their potential impact on integer factorization and cybersecurity.Our findings underscore the importance of quantum optimization and lay the foundation for future developments in quantum algorithmic enhancements,particularly within the Qiskit and Cirq quantum development environments.
文摘Shor proposed a polynomial time algorithm for computing the order of one element in a multiplicative group using a quantum computer. Based on Miller’s randomization, he then gave a factorization algorithm. But the algorithm has two shortcomings, the order must be even and the output might be a trivial factor. Actually, these drawbacks can be overcome if the number is an RSA modulus. Applying the special structure of the RSA modulus, an algorithm is presented to overcome the two shortcomings. The new algorithm improves Shor’s algorithm for factoring RSA modulus. The cost of the factorization algorithm almost depends on the calculation of the order of 2 in the multiplication group.
文摘Many classical encoding algorithms of vector quantization （VQ） of image compression that can obtain global optimal solution have computational complexity O（N）. A pure quantum VQ encoding algorithm with probability of success near 100% has been proposed, that performs operations 45√N times approximately. In this paper, a hybrid quantum VQ encoding algorithm between the classical method and the quantum algorithm is presented. The number of its operations is less than √N for most images, and it is more efficient than the pure quantum algorithm.
文摘Vector quantization （VQ） is an important data compression method. The key of the encoding of VQ is to find the closest vector among N vectors for a feature vector. Many classical linear search algorithms take O（N） steps of distance computing between two vectors. The quantum VQ iteration and corresponding quantum VQ encoding algorithm that takes O（√N） steps are presented in this paper. The unitary operation of distance computing can be performed on a number of vectors simultaneously because the quantum state exists in a superposition of states. The quantum VQ iteration comprises three oracles, by contrast many quantum algorithms have only one oracle, such as Shor＇s factorization algorithm and Grover＇s algorithm. Entanglement state is generated and used, by contrast the state in Grover＇s algorithm is not an entanglement state. The quantum VQ iteration is a rotation over subspace, by contrast the Grover iteration is a rotation over global space. The quantum VQ iteration extends the Grover iteration to the more complex search that requires more oracles. The method of the quantum VQ iteration is universal.
基金State Key Lab of Processors,Institute of Computing Technology,Chinese Academy of Sciences(CLQ202516)the Fundamental Research Funds for the Central Universities of China(3282025047,3282024051,3282024009)。
文摘The advent of Grover’s algorithm presents a significant threat to classical block cipher security,spurring research into post-quantum secure cipher design.This study engineers quantum circuit implementations for three versions of the Ballet family block ciphers.The Ballet‑p/k includes a modular-addition operation uncommon in lightweight block ciphers.Quantum ripple-carry adder is implemented for both“32+32”and“64+64”scale to support this operation.Subsequently,qubits,quantum gates count,and quantum circuit depth of three versions of Ballet algorithm are systematically evaluated under quantum computing model,and key recovery attack circuits are constructed based on Grover’s algorithm against each version.The comprehensive analysis shows:Ballet-128/128 fails to NIST Level 1 security,while when the resource accounting is restricted to the Clifford gates and T gates set for the Ballet-128/256 and Ballet-256/256 quantum circuits,the design attains Level 3.
基金Supported by the National High Technology Research and Development Program(No.2011AA010803)the National Natural Science Foundation of China(No.U1204602)
文摘In order to improve the attack efficiency of the New FORK-256 function, an algorithm based on Grover's quantum search algorithm and birthday attack is proposed. In this algorithm, finding a collision for arbitrary hash function only needs O(2m/3) expected evaluations, where m is the size of hash space value. It is proved that the algorithm can obviously improve the attack efficiency for only needing O(2 74.7) expected evaluations, and this is more efficient than any known classical algorithm, and the consumed space of the algorithm equals the evaluation.
文摘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.
基金supported by the National Natural Science Foundation of China(Grant No.61205108)the High Performance Computing(HPC)Foundation of National University of Defense Technology,China
文摘It is widely believed that Shor＇s factoring algorithm provides a driving force to boost the quantum computing research.However, a serious obstacle to its binary implementation is the large number of quantum gates. Non-binary quantum computing is an efficient way to reduce the required number of elemental gates. Here, we propose optimization schemes for Shor＇s algorithm implementation and take a ternary version for factorizing 21 as an example. The optimized factorization is achieved by a two-qutrit quantum circuit, which consists of only two single qutrit gates and one ternary controlled-NOT gate. This two-qutrit quantum circuit is then encoded into the nine lower vibrational states of an ion trapped in a weakly anharmonic potential. Optimal control theory（OCT） is employed to derive the manipulation electric field for transferring the encoded states. The ternary Shor＇s algorithm can be implemented in one single step. Numerical simulation results show that the accuracy of the state transformations is about 0.9919.
基金Supported by National Natural Science Foundation of China （ No. 60773065 ）.
文摘When the Grover＇ s original algorithm is applied to search an unordered database, the success probability decreases rapidly with the increase of marked items. Aiming at this problem, a general quantum search algorithm with small phase rotations is proposed. Several quantum search algorithms can be derived from this algorithm according to different phase rotations. When the size of phase rotations are fixed at 0. 01π, the success probability of at least 99. 99% can be obtained in 0（√N/M） iterations.
文摘The objective of this paper concerns at first the motivation and the method of Shor’s algorithm including remarks on quantum computing introducing an algorithmic description of the method.The corner stone of the Shor’s algorithm is the modular exponentiation that is themost computational component(in time and space).A linear depth unit based on phase estimation is introduced and a description of a generic version of a modular multiplier based on phases is introduced to build block of a gates to efficient modular exponentiation circuit.Our proposal includes numerical experiments achieved on both the IBM simulator using the Qiskit library and on quantum physical optimizers provided by IBM.The shor’s algorithm based on phase estimation succeeds in factoring integer numbers with more than 35 digits using circuits with about 100 qubits.
基金Project supported by the National Basic Research Program of China(Grant No.2013CB338002)the National Natural Science Foundation of China(Grant No.61502526)
文摘To overcome the difficulty of realizing large-scale quantum Fourier transform(QFT)within existing technology,this paper implements a resource-saving method(named t-bit semiclassical QFT over Z_(2n)),which could realize large-scale QFT using an arbitrary-scale quantum register.By developing a feasible method to realize the control quantum gate Rk,we experimentally realize the 2-bit semiclassical QFT over Z_(2-3)on IBM's quantum cloud computer,which shows the feasibility of the method.Then,we compare the actual performance of 2-bit semiclassical QFT with standard QFT in the experiments.The squared statistical overlap experimental data shows that the fidelity of 2-bit semiclassical QFT is higher than that of standard QFT,which is mainly due to fewer two-qubit gates in the semiclassical QFT.Furthermore,based on the proposed method,N=15 is successfully factorized by implementing Shor's algorithm.
文摘An optimal estimator of quantum states based on a modified Kalman’s filter is proposed in this work. Such estimator acts after a state measurement, allowing us to obtain an optimal estimate of the quantum state resulting in the output of any quantum algorithm. This method is much more accurate than other types of quantum measurements, such as, weak measurement, strong measurement, and quantum state tomography, among others.
