Quantum factorization of 143 on a dipolar-coupling nuclear magnetic resonance system

Quantum algorithms could be much faster than classical ones in solving the factoring problem. Adiabatic quantum computation for this is an alternative approach other than Shor's algorithm. Here we report an improved adiabatic factoring algorithm and its experimental realization to factor the number 143 on a liquid-crystal NMR quantum processor with dipole-dipole couplings. We believe this to be the largest number factored in quantum-computation realizations, which shows the practical importance of adiabatic quantum algorithms.     

Influence of superpositional wave function oscillations on Shor's quantum algorithm

We investigate the influence of superpositional wave function oscillations on the performance of Shor's quantum algorithm for factorization of integers. It is shown that wave function oscillations can modify the required quantum interference. This undesirable effect can be routinely eliminated using a resonant pulse implementation of quantum computation, but requires special analysis for nonresonant implementations. We also discuss the influence of this effect on implementation of other quantum algorithms.     

Experimental demonstration of a compiled version of Shor's algorithm with quantum entanglement

Shor's powerful quantum algorithm for factoring represents a major challenge in quantum computation. Here, we implement a compiled version in a photonic system. For the first time, we demonstrate the core processes, coherent control, and resultant entangled states required in a full-scale implementation. These are necessary steps on the path towards scalable quantum computing. Our results highlight that the algorithm performance is not the same as that of the underlying quantum circuit and stress the importance of developing techniques for characterizing quantum algorithms.     

Implementation of ternary Shor's algorithm based on vibrational states of an ion in anharmonic potential

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.     

Efficient factorization with a single pure qubit and logN mixed qubits

It is commonly assumed that Shor's quantum algorithm for the efficient factorization of a large number N requires a pure initial state. Here we demonstrate that a single pure qubit, together with a collection of log 2N qubits in an arbitrary mixed state, is sufficient to implement Shor's factorization algorithm efficiently.     

量子信息讲座续讲 第一讲 量子计算中的因子分解

因子分解对所有的现行计算机而言是难解的 .这是现在通用的公共加密系统的基础 .文章介绍了在量子计算机上进行的Shor量子算法 ,即利用量子态的相干叠加和纠缠特性以及量子逻辑门实现量子计算的方法 ;并着重从理论原理和实验实现这两方面说明利用余因子函数和离散傅里叶变换使这种量子算法对因子分解是有效的 .     

Design of quantum VQ iteration and quantum VQ encoding algorithm taking O（√N） steps for data compression

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.     

Experimental realization of an order-finding algorithm with an NMR quantum computer

We report the realization of a nuclear magnetic resonance quantum computer which combines the quantum Fourier transform with exponentiated permutations, demonstrating a quantum algorithm for order finding. This algorithm has the same structure as Shor's algorithm and its speed-up over classical algorithms scales exponentially. The implementation uses a particularly well-suited five quantum bit molecule and was made possible by a new state initialization procedure and several quantum control techniques.     

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.     

Realization of -bit semiclassical quantum Fourier transform on IBM's quantum cloud computer

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_(2~n)), 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.