• 中国精品科技期刊
  • CCF推荐A类中文期刊
  • 计算领域高质量科技期刊T1类
Advanced Search

2021  Vol. 58  No. 9

Abstract:
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.
Abstract:
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.
Abstract:
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.
Abstract:
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.
Abstract:
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.
Abstract:
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.
Abstract:
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.
Abstract:
Document grounded conversations is an emerging hot task in the field of dialogue system. Different from previous tasks, it needs to consider both the utterances and the given document. However, previous work focused on the relationship between the two, but ignored the utterances’ difference in the effect of response generation. To solve this problem, a new dialectical approach to the dialogue history, which means the utterances before the last one, is proposed in this paper. At the encoding step, it divides the modeling of the semantic information into two parts: using history and ignoring history, and then uses the comparative integration method to summarize the branch results. In this way, when the dialogue history is not related to the current utterance, it can avoid being introduced as noise which will damage the performance of the model. Besides, it also strengthens the guiding role of the current utterance in the information filtering process. Experimental results show that compared with the existing baselines, this model can generate responses that are more in line with the current context and more informative, indicating that it can better understand dialogue information and conduct knowledge filtering. And through the ablation study, the effectiveness of each module in the modeling process is also verified.
Abstract:
NLIDB (natural language interface to database) provides a new form to access databases with barrier-free text query, which reduces the burdens for users to learn the SQL (structured query language). Because of its great application value, NLIDB has attracted much attention in the field of scientific research and commercial in recent years. Most of the current mature NLIDB systems are based on classical natural language processing technologies, which depend on rule-based approaches to realize the transformation from natural language questions to SQL. But these approaches have poor ability to generalize. Deep learning models have advantages on distributed and high-level representation learning, which are competent for semantic feature mining in natural language. Therefore, the application of deep learning technology in NLIDB has gradually become a hot research topic nowadays. This paper provides a systematic review of the NLIDB researches based on deep learning in recent years. The main contributions are as follows: firstly, according to the decoding method, we sort out existing deep learning-based NLIDB models into 4 categories, and state the advantage and the weakness respectively; secondly, we summarize 7 common assist techniques in the implementations of the NLIDB models; thirdly, we propose the problems remaining to be solved and put forward the relevant directions for future researches.
Abstract:
Image captioning combines the two research fields of computer vision and natural language processing. It requires not only complete image semantic understanding, but also complex natural language expression. It is a crucial task for further research on visual intelligence in line with human perception. This paper reviews the research progress on image captioning. Firstly, five key technologies involved in current deep learning based image captioning methods are summarized and analyzed, including overall architecture, learning strategy, feature mapping, language model and attention mechanism. Then, according to the development process, the existing image captioning methods are divided into four categories, i.e. template based methods, retrieval based methods, encoder-decoder architecture based methods and compositional architecture based methods. We describe the basic concepts, representative methods and research status of each category. Furthermore, we emphatically discuss the various methods based on encoder-decoder architecture and their innovative ideas, such as multimodal space, visual space, semantic space, attention mechanism, model optimization, and so on. Subsequently, from the experimental point of view, we show the common benchmark datasets and evaluation measures in the field of image captioning. In addition, we compare the performance of some typical methods on two benchmark datasets. Finally, based on improving the accuracy, integrity, novelty and diversity of image caption, several future development trends of image captioning are presented.
Abstract:
In the Internet era, the explosive rise of information and unprecedented data size has greatly exceeded the receivers’ receiving and handling capability. Accordingly it has become a necessity to capture important and useful information from the massive and complex data. The problem of information overload calls for a more efficient information filtering system and this explains the birth and rise of the recommendation system. In the real recommendation situations, the long tail phenomenon is typically represented, whether in the customers’ rating or their frequency of opting for the items. Actually a deep analysis on the long tail phenomenon helps to promote the e-commerce stakeholders’ performance as well as explore the customers’ preferences, which explains the increasing attention paid on the long tail recommendation. To handle the interpretability of long tail recommendation, a three-factor probabilistic graphical model is proposed. To meet the recommendation system and users’ need for interpretable item recommendation in reality, a three-factor probabilistic graphical recommendation method based on customers’ activity level, the items’unpopularity and customer-item preference level are proposed. In this method, the advantage of probabilistic graphical model in interpreting cause-result relationship is utilized and recommendation accuracy and design novelty in the algorithm can be ensured in this study. The results of experiments indicate that with the advantage of interpretability, the three-factor probabilistic graphical recommendation method can ensure prediction accuracy and perform better in providing novel recommendations.
Abstract:
Graph convolutional network is a deep learning model for graph structure data, and it has become a very hot approach in the research of recommendation system due to its powerful ability in feature extraction and representation of data. This paper focuses on the rating prediction tasks in recommendation system, and points out two deficiencies of existing graph convolutional network based recommendation models by detailed analysis, including making use of first-order collaborative signals only and ignoring the differences of user opinions. For solving them, an end-to-end enhanced graph convolutional network based collaborative recommendation model is proposed. It adopts an enhanced graph convolutional layer to take full advantage of collaborative signals to learn embeddings of users and items on graph, which aggregates second-order collaborative signals and incorporates the influence of different user opinions. And it also stacks several graph convolutional layers to iteratively refine the embeddings and finally uses a nonlinear multilayer perceptron network to make rating prediction. The experiments on 5 benchmark recommendation datasets show that the proposed model achieves lower prediction errors compared with several state-of-the-art graph convolutional network based recommendation models.
Abstract:
Recently, studies on domain adaptation have shown the effectiveness of adversarial learning in filling the differences between two domains, but there are still some limitations that samples taken from two domains are not enough to keep the domain invariance in potential spaces. Inspired by the fact that CapsNet(capsule network) has a strong ability to extract the invariance of features from samples, we introduce it into the domain adaptation problem. Firstly, a new convolution algorithm is devised over capsule-layer, combined with residual block, which makes it possible to train a deeper CapsNet. Results demonstrate that this new structure of CapsNet has a stronger ability to extract features. Secondly, the traditional adversarial discriminative adaptation methods have the defect that prones to blur the boundary between different domains, which in turn leads to a decline in the discriminative performance. Inspired by VAE-GAN(variational auto-encoder, generative adversarial networks), we use a reconstruction network as a strong constraint, so that the adversarial discriminative network avoids the inherent defect of mode collapse when the convolution base is transferring, and ensures that the discriminator is sensitive to the invariance of representation in different domains. Experiments on standard datasets show that our model achieves better performance in domain adaptation tasks of varying complexity.
Abstract:
Massive online interview video data provides an important data basis for intelligent interview evaluation. With the spread of the current global epidemic, the demand for online interviews has increased, as well as the intelligent interview evaluation tools. In a structured interview, the interviewer needs to observe the interviewee’s answers based on the evaluation criteria, and form a profile evaluation of the interviewee’s personality traits, communication skills, and leadership, so as to judge whether the interviewee’s characteristics match the position. Among them, personality evaluation is a widely accepted evaluation method among companies. Because personality traits affect people’s language expression, interpersonal communication and other aspects, it is an important reference to assist the interviewer to decide whether an interviewee meets their job requirements. Based on this, a fine-grained interview evaluation method based on the long short term memory (LSTM) and the hierarchical keyword-question attention mechanism (HKQA-LSTM) is proposed, which aims to score the different personality dimensions of the interviewees and obtain a comprehensive interview score based on this. First, we effectively filter out important words and sentences that are closely related to personality traits in the interview dialogue by introducing a keyword attention mechanism. Then, we use keyword-question level attention mechanism and two-stage model learning mechanism on this basis, and fully combine the multi-scale contextual features of the texts expressed by interviewees to accurately predict personality traits. Finally, through the fusion of personality traits, a comprehensive interpretive evaluation result of the interview is obtained. The experimental results based on real interview scene data show that this method can effectively evaluate the interviewees’ different personality traits scores and accurately predict the interviewees’ overall scores.
Abstract:
As edge computing and cloud computing develop in a rapid speed and integrate with each other, resources and services gradually offload from the core network to the edge of the network. Efficient computation offloading algorithm is one of the most important problems in mobile edge computing networks. In order to improve the performance of the algorithm, a computation offloading algorithm with path selection based on K-shell influence maximization is proposed. The K-shell method is used to grade the edge servers by applying the convertibility and maximizing influence model of similar problems. Otherwise, considering the problem of excessive load of edge servers, path overlap (PO) algorithm is constructed, and indicators such as the communication quality, interaction strength, and queue processing ability, etc. are introduced to optimize the performance of the algorithm. The offloading path problem of the optimization calculation task is transformed into the social network impact maximization problem. Based on the idea of maximizing K-shell influence, greedy and heuristic algorithms are optimized and improved, and the K-shell influence maximization computation offloading (Ks-IMCO) algorithm is proposed to solve the problem of computational offloading. Through the comparative analysis of Ks-IMCO and random allocation (RA), path selection with handovers (PSwH) algorithm experiments, the energy consumption and delay of Ks-IMCO algorithm have been significantly improved, which can effectively improve the efficiency of edge computing network computing offloading.
Abstract:
Text classification is an essential task in natural language processing. The high dimension and sparsity of text data bring many problems and challenges to text classification. Naive Bayes (NB) is widely used in text classification due to its simplicity, efficiency and comprehensibility, but its attribute conditional independence assumption is rarely met in real-world text data and thus affects its classification performance. In order to weaken the attribute conditional independence assumption required by NB, scholars have proposed a variety of improved approaches, mainly including structure extension, instance selection, instance weighting, feature selection, and feature weighting. However, all these approaches construct NB classification models based on the independent term features, which restricts their classification performance to a certain extent. In this paper, we try to improve the naive Bayes text classification model by feature learning and thus propose a two-layer Bayes model called random forest naive Bayes (RFNB). RFNB is divided into two layers. In the first layer, random forest (RF) is used to learn high-level features of term combinations from original term features. Then the learned new features are input into the second layer, which is used to construct a Bernoulli naive Bayes model after one-hot encoding. The experimental results on a large number of widely used text datasets show that the proposed RFNB significantly outperforms the existing state-of-the-art naive Bayes text classification models and other classical text classification models.
Abstract:
Car accident prediction is an important problem to study for avoiding the accidents. Previous studies make the prediction for a car based either on macro factors such as geography, environment and traffic or on micro factors such as car and driver behaviors. There is rarely a study combining the two types of factors because it is difficult to collect the two types of data at the same time. However, car accidents usually result from both of the two types of factors. In addition, the current researches predict whether an accident will happen or not. There is rarely a study providing a more accurate accident probability because there is no probability label for use in the collected data. However, such a probability is useful to notify the driver in different warning levels. The OSU(Ohio State University) accident dataset of macro factors published in 2019 has some identical characteristics with the FARS(fatality analysis reporting system) dataset of macro factors and SHRP2(strategic highway research program 2) dataset of micro factors, and thus provides an opportunity to fuse them. Therefore in this paper, we obtain a dataset of both macro and micro factors. In the dataset, accident data (positive data) is fused from the OSU and FARS datasets, as well as Sim-SHRP2(simulated strategic highway research program 2) similar to the SHRP2 dataset, while safe-driving data (negative data) is obtained by ourselves driving a car. In addition, since the obtained dataset does not have any probability label, we also design a probability-level unsupervised deep learning framework to predict the accurate probability. The framework iteratively generates accurate probabilities from the obtained dataset, and is trained with the generated probabilities. The experimental results indicate our framework can predict car accidents with the obtained dataset sensitively and accurately.
Abstract:
In order to reveal the deeper essential characteristics of hesitant fuzzy rough approximation operators and further study the relationship between hesitant fuzzy rough approximation spaces and hesitant fuzzy topological spaces, it is of great significance to study the axiomatic characterizations of hesitant fuzzy rough approximation operators. In most of the existing results, the axioms used to describe hesitant fuzzy approximation operators contain multiple axioms. Since the axiomatic characterization of approximation operator is a key method in the research of the mathematical structure of rough set theory, it is a fundamental problem in axiomatic method to find the minimum set of abstract axioms. In view of the above problems, this paper focuses on the study of characterization by using single axiom. The number of axioms in the axiom set is simplified to unique axiom for the first time, and a new axiom description is proposed. First of all, the axiomatic characterizations of classical hesitant fuzzy rough approximation operators are given. Then, we study the problem of the axiomatization of hesitant fuzzy rough approximation operators generated by serial, reflexive, symmetric, transitive and equivalent hesitant fuzzy relations, respectively. Finally, it is proved that the hesitant fuzzy rough approximation space can induce a hesitant fuzzy topological space.