ISSN 1000-1239 CN 11-1777/TP



    Default Latest Most Read
    Please wait a minute...
    For Selected: Toggle Thumbnails
    Journal of Computer Research and Development    2021, 58 (9): 1821-1822.   DOI: 10.7544/issn1000-1239.2021.qy0901
    Abstract108)      PDF (211KB)(112)       Save
    Related Articles | Metrics
    An Overview of Quantum Optimization
    He Jianhao Li Lüzhou
    Journal of Computer Research and Development    2021, 58 (9): 1823-1834.   DOI: 10.7544/issn1000-1239.2021.20210276
    Abstract360)      PDF (688KB)(347)       Save
    Quantum optimization has attracted much attention in recent years. It mainly studies how to accelerate the solution of optimization problems with quantum computing. This overview will classify the quantum optimization algorithm according to whether the optimization variable is continuous, and focus on introducing the continuous variable optimization algorithm. Through the investigation of existing work, this article obtains the following observations: 1)The works of discrete variable quantum optimization were distributed five years ago, while the works of continuous variable quantum optimization has attracted more attention in the last five years; 2)The main basic technologies used in quantum optimization were mainly proposed ten to twenty years ago, and basic innovations are needed; 3)In most works of quantum optimization, theoretical acceleration of time complexity or query complexity is achieved, but more rigorous theoretical analysis is still needed; 4)There are still many problems worthy of exploration by quantum computing researchers in the optimization field, especially in the field of non-convex optimization, which is considered to be difficult in classical computing.
    Related Articles | Metrics
    Quantum Algorithm for Spectral Regression
    Pan Shijie, Gao Fei, Wan Linchun, Qin Sujuan, Wen Qiaoyan
    Journal of Computer Research and Development    2021, 58 (9): 1835-1842.   DOI: 10.7544/issn1000-1239.2021.20210366
    Abstract66)      PDF (600KB)(88)       Save
    Subspace learning is an important research direction in the field of machine learning. In order to reduce the complexity of subspace learning, Cai et al. proposed a spectral regression dimensionality reduction framework, and proposed efficient spectral regression for subspace learning that constructed their graph by incorporating the label information. In recent years, the development of quantum computing has made it possible to further reduce the complexity of subspace learning algorithms. Meng et al. pioneered the quantum algorithm for spectral regression (MYXZ algorithm). In this article, the limitations of the MYXZ algorithm are pointed out. We point out that MYXZ algorithm uses sparse Hamiltonian simulation technology to process the matrix generated by the weight matrix, but this matrix is a dense matrix in some cases. In response to this situation, we propose an improved quantum spectral regression algorithm. Our improved algorithm uses quantum singular value estimation technology, which has a polynomial acceleration compared with MYXZ algorithm when dealing with dense matrices. In addition, we propose a new quantum algorithm to accelerate the classical efficient spectral regression. The problems that our new algorithm can handle cannot be handled by MYXZ algorithm. Our algorithm utilizes quantum ridge regression and quantum matrix vector multiplication technology. Under the same parameter conditions, our algorithm has polynomial acceleration effect compared with the classical algorithm.
    Related Articles | Metrics
    Quantum Error Mitigation: A Review
    Zhang Yukun
    Journal of Computer Research and Development    2021, 58 (9): 1843-1855.   DOI: 10.7544/issn1000-1239.2021.20210367
    Abstract68)      PDF (1087KB)(88)       Save
    Due to the interaction with the environment and imperfections of controls, quantum devices are accompanied with errors, whose accumulation could lead to a meaningless computing result. The realization of a full-fledged quantum computer relies on quantum error correction, which however, introduces a huge overhead that makes it challenging for near-term quantum devices. In the noisy intermediate-scale quantum era, quantum error mitigation methods instead of quantum error correction are introduced for suppressing errors. Using a mild cost under reasonable assumptions, quantum error mitigation could enhance the result to achieve a desired computational accuracy, and its feasibility has been demonstrated extensively in theories and experiments. This article aims to introduce and summarize the latest developments in quantum error mitigation, and to comment on potential future directions.
    Related Articles | Metrics
    An Investigation into Quantum Program Mapping on Superconducting Quantum Computers
    Dou Xinglei, Liu Lei, Chen Yuetao
    Journal of Computer Research and Development    2021, 58 (9): 1856-1874.   DOI: 10.7544/issn1000-1239.2021.20210314
    Abstract64)      PDF (2887KB)(82)       Save
    Errors occur due to noise when quantum programs are running on a quantum computer. Previous quantum program mapping solutions map a specific quantum program onto the most reliable region on a quantum computer for higher fidelity. Mapping multiple quantum programs onto a specific quantum computer simultaneously improves the throughput and resource utilization of the quantum computer. However, due to the scarcity of robust resources and resource allocation conflict, multi-programming on quantum computers leads to a decline in overall fidelity. We introduce quantum program mapping, classify the related studies, and analyze their characteristics and differences. Furthermore, we propose a new mapping solution for mapping concurrent quantum programs, including three key designs. 1) We propose a community detection assisted qubit partition (CDAQP) algorithm, which partitions physical qubits for concurrent quantum programs according to both physical topology and the error rates, improving the reliability of initial mapping and avoiding the waste of robust resources. 2) We introduce inter-program SWAPs, reducing the mapping overheads of concurrent quantum programs. 3) A framework for scheduling quantum program mapping tasks is proposed, which dynamically selects concurrent quantum programs to be executed, improving the throughput while ensuring the fidelity of the quantum computers. Our approach improves the fidelity by 8.6% compared with the previous solution while reducing the mapping overheads by 11.6%. Our system is a prototype of the OS for quantum computers—QuOS.
    Related Articles | Metrics
    A Heterogeneous Quantum-Classical Computing System Targeting Noisy Intermediate-Scale Quantum Technology
    Fu Xiang, Zheng Yuzhen, Su Xing, Yu Jintao, Xu Weixia, Wu Junjie
    Journal of Computer Research and Development    2021, 58 (9): 1875-1896.   DOI: 10.7544/issn1000-1239.2021.20210368
    Abstract62)      PDF (3730KB)(101)       Save
    Quantum computers promise to accelerate solving problems that are intractable by classical computers, such as prime factorization and quantum chemistry simulation. It has been demonstrated that a single quantum system can integrate more than fifty noisy solid-state qubits and surpass contemporary classical computers in specific computing tasks, marking the arrival of the noisy intermediate-scale quantum (NISQ) era. As more and more qubits can be integrated into a single system, how to integrate qubits with control hardware, software development environment, and classical computing resources to obtain a complete and usable quantum computing system is a problem that needs to be further clarified. By comparing both the control and execution of quantum and classical computing, this paper proposes a heterogeneous quantum-classical system targeting the NISQ technology. Taking a typical NISQ algorithm (the iterative phase estimation algorithm) as an example, this paper introduces the whole process of executing a quantum algorithm and related software and hardware, including the high-level programming language, compiler, quantum software and hardware interface, and control microarchitecture. On top of it, this paper discusses the challenges confronting each layer in the NISQ era. This paper aims to provide a general introduction of quantum computing systems to readers (especially beginners of quantum computing) from an engineering perspective, hoping to promote people’s understanding of the overall architecture of quantum computing systems in the NISQ era and stimulate more related research.
    Related Articles | Metrics
    Dynamics of Coherence in Quantum Walk with Two Coins
    Li Meng
    Journal of Computer Research and Development    2021, 58 (9): 1897-1905.   DOI: 10.7544/issn1000-1239.2021.20210266
    Abstract44)      PDF (519KB)(52)       Save
    Quantum walk is an important model of quantum computing, and quantum walk with multiple coins has attracted more and more attention due to its outstanding performance in quantum communication protocols. Quantum coherence can not only describe the characteristics of quantum states, but also reflect the properties of quantum evolution process. In this paper, we analyze quantum coherence for the model of quantum walk with two coins on the one dimensional circle. On the one hand, we discuss the influence of the choice of initial quantum state and coin operators on quantum coherence. When the coin operator is Hadamard operator, as long as the initial state in subspace is equal superposition, the whole evolutionary process of quantum walk is periodic, and quantum coherence only depends on the number of vertexes of the circle and steps; When the initial state is equal superposition and there are no limits on the coin operators, the evolution of the quantum state is also extremely regular. On the other hand, we find that in the process of perfect state transfer by quantum walk, the coin operator will determine the quantum coherence directly. In addition, we also discuss the equivalence between the two quantum walk models, and based on this, we point out the possibility of application and improvement in quantum teleportation.
    Related Articles | Metrics
    Quantum Hypothesis Testing Mutual Information
    Zhang Shuyi Xi Zhengjun
    Journal of Computer Research and Development    2021, 58 (9): 1906-1914.   DOI: 10.7544/issn1000-1239.2021.20210346
    Abstract47)      PDF (508KB)(53)       Save
    von Neumann mutual information is a generalization of Shannon mutual information in quantum information theory, and it has been found to have useful applications in the channel capacity. The many classical quantifiers can be extended for pairs of quantum states in various inequivalent ways, due to the non-commutativity of quantum states. Quantum hypothesis testing relative entropy comes from the hypothesis testing question, and it is one of the most fundamental primitives in quantum information processing. We discuss the quantum mutual information with respect to quantum hypothesis testing relative entropy. We give some properties of quantum hypothesis testing relative entropy, and give the relationships between it and other quantum generalized entropies. Using relative entropy, we define quantum hypothesis testing mutual information, and exhibit some properties, such as, data processing inequality. Using the sum between mutual information and condition entropy, we discuss the chain rules, which are generally an important technical tool in information theory.
    Related Articles | Metrics