Factoring larger integers with fewer qubits via quantum annealing with optimized parameters

RSA cryptography is based on the difficulty of factoring large integers, which is an NP-hard(and hence intractable) problem for a classical computer. However, Shor's algorithm shows that its complexity is polynomial for a quantum computer, although technical difficulties mean that practical quantum computers that can tackle integer factorizations of meaningful size are still a long way away. Recently, Jiang et al. proposed a transformation that maps the integer factorization problem onto the quadratic unconstrained binary optimization(QUBO) model. They tested their algorithm on a D-Wave 2000 Q quantum annealing machine, raising the record for a quantum factorized integer to 376289 with only 94 qubits. In this study, we optimize the problem Hamiltonian to reduce the number of qubits involved in the final Hamiltonian while maintaining the QUBO coefficients in a reasonable range, enabling the improved algorithm to factorize larger integers with fewer qubits. Tests of our improved algorithm using D-Wave's hybrid quantum/classical simulator qbsolv confirmed that performance was improved, and we were able to factorize 1005973, a new record for quantum factorized integers, with only 89 qubits. In addition, our improved algorithm can tolerate more errors than the original one. Factoring 1005973 using Shor's algorithm would require about 41 universal qubits,which current universal quantum computers cannot reach with acceptable accuracy. In theory, the latest IBM Q System OneTM(Jan. 2019) can only factor up to 10-bit integers, while the D-Wave have a thousand-fold advantage on the factoring scale. This shows that quantum annealing machines, such as those by D-Wave, may be close to cracking practical RSA codes, while universal quantum-circuit-based computers may be many years away from attacking RSA.

Traffic Clustering Algorithm of Urban Data Brain Based on a Hybrid-Augmented Architecture of Quantum Annealing and Brain-Inspired Cognitive Computing

In recent years,the urbanization process has brought modernity while also causing key issues,such as traffic congestion and parking conflicts.Therefore,cities need a more intelligent"brain"to form more intelligent and efficient transportation systems.At present,as a type of machine learning,the traditional clustering algorithm still has limitations.K-means algorithm is widely used to solve traffic clustering problems,but it has limitations,such as sensitivity to initial points and poor robustness.Therefore,based on the hybrid architecture of Quantum Annealing(QA)and brain-inspired cognitive computing,this study proposes QA and Brain-Inspired Clustering Algorithm(QABICA)to solve the problem of urban taxi-stand locations.Based on the traffic trajectory data of Xi’an and Chengdu provided by Didi Chuxing,the clustering results of our algorithm and K-means algorithm are compared.We find that the average taxi-stand location bias of the final result based on QABICA is smaller than that based on K-means,and the bias of our algorithm can effectively reduce the tradition K-means bias by approximately 42%,up to approximately 83%,with higher robustness.QA algorithm is able to jump out of the local suboptimal solutions and approach the global optimum,and brain-inspired cognitive computing provides search feedback and direction.Thus,we will further consider applying our algorithm to analyze urban traffic flow,and solve traffic congestion and other key problems in intelligent transportation.

Optimization of Quantum Computing Models Inspired by D-Wave Quantum Annealing

With the slow progress of universal quantum computers,studies on the feasibility of optimization by a dedicated and quantum-annealing-based annealer are important.The quantum principle is expected to utilize the quantum tunneling effects to find the optimal solutions for the exponential-level problems while classical annealing may be affected by the initializations.This study constructs a new Quantum-Inspired Annealing(QIA)framework to explore the potentials of quantum annealing for solving Ising model with comparisons to the classical one.Through various configurations of the 1 D Ising model,the new framework can achieve ground state,corresponding to the optimum of classical problems,with higher probability up to 28%versus classical counterpart(22%in case).This condition not only reveals the potential of quantum annealing for solving the Ising-like Hamiltonian,but also contributes to an improved understanding and use of the quantum annealer for various applications in the future.

New Advanced Computing Architecture for Cryptography Design and Analysis by D-Wave Quantum Annealer

Universal quantum computers are far from achieving practical applications.The D-Wave quantum computer is initially designed for combinatorial optimizations.Therefore,exploring the potential applications of the D-Wave device in the field of cryptography is of great importance.First,although we optimize the general quantum Hamiltonian on the basis of the structure of the multiplication table(factor up to 1005973),this study attempts to explore the simplification of Hamiltonian derived from the binary structure of the integers to be factored.A simple factorization on 143 with four qubits is provided to verify the potential of further advancing the integer-factoring ability of the D-Wave device.Second,by using the quantum computing cryptography based on the D-Wave 2000 Q system,this research further constructs a simple version of quantum-classical computing architecture and a Quantum-Inspired Simulated Annealing(QISA)framework.Good functions and a high-performance platform are introduced,and additional balanced Boolean functions with high nonlinearity and optimal algebraic immunity can be found.Further comparison between QISA and Quantum Annealing(QA)on six-variable bent functions not only shows the potential speedup of QA,but also suggests the potential of architecture to be a scalable way of D-Wave annealer toward a practical cryptography design.