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.展开更多
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.展开更多
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.展开更多
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.展开更多
The elliptic curve discrete logarithm problem(ECDLP)is a popular choice for cryptosystems due to its high level of security.However,with the advent of the extended Shor’s algorithm,there is concern that ECDLP may soo...The elliptic curve discrete logarithm problem(ECDLP)is a popular choice for cryptosystems due to its high level of security.However,with the advent of the extended Shor’s algorithm,there is concern that ECDLP may soon be vulnerable.While the algorithm does ofer hope in solving ECDLP,it is still uncertain whether it can pose a real threat in practice.From the perspective of the quantum circuits of the algorithm,this paper analyzes the feasibility of cracking ECDLP using an ion trap quantum computer with improved quantum circuits for the extended Shor’s algorithm.We give precise quantum circuits for extended Shor’s algorithm to calculate discrete logarithms on elliptic curves over prime felds,including modular subtraction,three diferent modular multiplication,and modular inverse.Additionally,we incorporate and improve upon windowed arithmetic in the circuits to reduce the CNOTcounts.Whereas previous studies mostly focused on minimizing the number of qubits or the depth of the circuit,we focus on minimizing the number of CNOT gates in the circuit,which greatly afects the running time of the algorithm on an ion trap quantum computer.Specifcally,we begin by presenting implementations of basic arithmetic operations with the lowest known CNOT-counts,along with improved constructions for modular inverse,point addition,and windowed arithmetic.Next,we precisely estimate that,to execute the extended Shor’s algorithm with the improved circuits to factor an n-bit integer,the CNOT-count required is1237n^(3)/log n+2n^(2)+n.Finally,we analyze the running time and feasibility of the extended Shor’s algorithm on an ion trap quantum computer.展开更多
This research paper analyzes the urgent topic of quantum cybersecurity and the current federal quantum-cyber landscape. Quantum-safe implementations within existing and future Internet of Things infrastructure are dis...This research paper analyzes the urgent topic of quantum cybersecurity and the current federal quantum-cyber landscape. Quantum-safe implementations within existing and future Internet of Things infrastructure are discussed, along with quantum vulnerabilities in public key infrastructure and symmetric cryptographic algorithms. Other relevant non-encryption-specific areas within cybersecurity are similarly raised. The evolution and expansion of cyberwarfare as well as new developments in cyber defense beyond post-quantum cryptography and quantum key distribution are subsequently explored, with an emphasis on public and private sector awareness and vigilance in maintaining strong security posture.展开更多
As technological innovations in computers begin to advance past their limit (Moore’s law), a new problem arises: What computational device would emerge after the classical supercomputers reach their physical limitati...As technological innovations in computers begin to advance past their limit (Moore’s law), a new problem arises: What computational device would emerge after the classical supercomputers reach their physical limitations? At this moment in time, quantum computers are at their starting stage and there are already some strengths and advantages when compared with modern, classical computers. In its testing period, there are a variety of ways to create a quantum computer by processes such as the trapped-ion and the spin-dot methods. Nowadays, there are many drawbacks with quantum computers such as issues with decoherence and scalability, but many of these issues are easily emended. Nevertheless, the benefits of quantum computers at the moment outweigh the potential drawbacks. These benefits include its use of many properties of quantum mechanics such as quantum superposition, entanglement, and parallelism. Using these basic properties of quantum mechanics, quantum computers are capable of achieving faster computational times for certain problems such as finding prime factors of an integer by using Shor’s algorithm. From the advantages such as faster computing times in certain situations and higher computing powers than classical computers, quantum computers have a high probability to be the future of computing after classical computers hit their peak.展开更多
Quantum technologies,mainly quantum computing and quantum sensing are emerging as new applications of quantum mechanics for practical use.Two notable advancements in quantum computing and quantum sensing respectively ...Quantum technologies,mainly quantum computing and quantum sensing are emerging as new applications of quantum mechanics for practical use.Two notable advancements in quantum computing and quantum sensing respectively are Shor’s algorithm and nitrogen vacancy centers in diamond lattices.Shor’s algorithm leverages certain properties of quantum computers to factor large numbers faster than any classical algorithm.Nitrogen vacancy centers leverage spin defects to sense even very small signatures of magnetic fields.This review article aims to provide a pedagogical introduction and overview of these emerging platforms for quantum technology.展开更多
文摘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.
基金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.
文摘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.
文摘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.
基金supported by National Natural Science Foundation of China(Grant No.61672517)National Natural Science Foundation of China(Key Program,Grant No.61732021).
文摘The elliptic curve discrete logarithm problem(ECDLP)is a popular choice for cryptosystems due to its high level of security.However,with the advent of the extended Shor’s algorithm,there is concern that ECDLP may soon be vulnerable.While the algorithm does ofer hope in solving ECDLP,it is still uncertain whether it can pose a real threat in practice.From the perspective of the quantum circuits of the algorithm,this paper analyzes the feasibility of cracking ECDLP using an ion trap quantum computer with improved quantum circuits for the extended Shor’s algorithm.We give precise quantum circuits for extended Shor’s algorithm to calculate discrete logarithms on elliptic curves over prime felds,including modular subtraction,three diferent modular multiplication,and modular inverse.Additionally,we incorporate and improve upon windowed arithmetic in the circuits to reduce the CNOTcounts.Whereas previous studies mostly focused on minimizing the number of qubits or the depth of the circuit,we focus on minimizing the number of CNOT gates in the circuit,which greatly afects the running time of the algorithm on an ion trap quantum computer.Specifcally,we begin by presenting implementations of basic arithmetic operations with the lowest known CNOT-counts,along with improved constructions for modular inverse,point addition,and windowed arithmetic.Next,we precisely estimate that,to execute the extended Shor’s algorithm with the improved circuits to factor an n-bit integer,the CNOT-count required is1237n^(3)/log n+2n^(2)+n.Finally,we analyze the running time and feasibility of the extended Shor’s algorithm on an ion trap quantum computer.
文摘This research paper analyzes the urgent topic of quantum cybersecurity and the current federal quantum-cyber landscape. Quantum-safe implementations within existing and future Internet of Things infrastructure are discussed, along with quantum vulnerabilities in public key infrastructure and symmetric cryptographic algorithms. Other relevant non-encryption-specific areas within cybersecurity are similarly raised. The evolution and expansion of cyberwarfare as well as new developments in cyber defense beyond post-quantum cryptography and quantum key distribution are subsequently explored, with an emphasis on public and private sector awareness and vigilance in maintaining strong security posture.
文摘As technological innovations in computers begin to advance past their limit (Moore’s law), a new problem arises: What computational device would emerge after the classical supercomputers reach their physical limitations? At this moment in time, quantum computers are at their starting stage and there are already some strengths and advantages when compared with modern, classical computers. In its testing period, there are a variety of ways to create a quantum computer by processes such as the trapped-ion and the spin-dot methods. Nowadays, there are many drawbacks with quantum computers such as issues with decoherence and scalability, but many of these issues are easily emended. Nevertheless, the benefits of quantum computers at the moment outweigh the potential drawbacks. These benefits include its use of many properties of quantum mechanics such as quantum superposition, entanglement, and parallelism. Using these basic properties of quantum mechanics, quantum computers are capable of achieving faster computational times for certain problems such as finding prime factors of an integer by using Shor’s algorithm. From the advantages such as faster computing times in certain situations and higher computing powers than classical computers, quantum computers have a high probability to be the future of computing after classical computers hit their peak.
文摘Quantum technologies,mainly quantum computing and quantum sensing are emerging as new applications of quantum mechanics for practical use.Two notable advancements in quantum computing and quantum sensing respectively are Shor’s algorithm and nitrogen vacancy centers in diamond lattices.Shor’s algorithm leverages certain properties of quantum computers to factor large numbers faster than any classical algorithm.Nitrogen vacancy centers leverage spin defects to sense even very small signatures of magnetic fields.This review article aims to provide a pedagogical introduction and overview of these emerging platforms for quantum technology.
