Search

Restricted Boltzmann Machines (RBMs) are widely used probabilistic undirected graphical models with visible and latent nodes, playing an important role in statistics and machine learning. The task of structure learning for RBMs involves inferring the underlying graph by using samples from the visible nodes. Specifically, learning the two-hop neighbors of each visible node allows for the inference of the graph structure. Prior research has addressed the structure learning problem for specific classes of RBMs, namely ferromagnetic and locally consistent RBMs. In this paper, we extend the scope to the quantum computing domain and propose corresponding quantum algorithms for this problem. Our study demonstrates that the proposed quantum algorithms yield a polynomial speedup compared to the classical algorithms for learning the structure of these two classes of RBMs., Comment: 9 pages, 1 figure

The complete learning of an $n$-qubit quantum state requires samples exponentially in $n$. Several works consider subclasses of quantum states that can be learned in polynomial sample complexity such as stabilizer states or high-temperature Gibbs states. Other works consider a weaker sense of learning, such as PAC learning and shadow tomography. In this work, we consider learning states that are close to neural network quantum states, which can efficiently be represented by a graphical model called restricted Boltzmann machines (RBMs). To this end, we exhibit robustness results for efficient provable two-hop neighborhood learning algorithms for ferromagnetic and locally consistent RBMs. We consider the $L_p$-norm as a measure of closeness, including both total variation distance and max-norm distance in the limit. Our results allow certain quantum states to be learned with a sample complexity \textit{exponentially} better than naive tomography. We hence provide new classes of efficiently learnable quantum states and apply new strategies to learn them.

Video moment retrieval pursues an efficient and generalized solution to identify the specific temporal segments within an untrimmed video that correspond to a given language description. To achieve this goal, we provide a generative diffusion-based framework called MomentDiff, which simulates a typical human retrieval process from random browsing to gradual localization. Specifically, we first diffuse the real span to random noise, and learn to denoise the random noise to the original span with the guidance of similarity between text and video. This allows the model to learn a mapping from arbitrary random locations to real moments, enabling the ability to locate segments from random initialization. Once trained, MomentDiff could sample random temporal segments as initial guesses and iteratively refine them to generate an accurate temporal boundary. Different from discriminative works (e.g., based on learnable proposals or queries), MomentDiff with random initialized spans could resist the temporal location biases from datasets. To evaluate the influence of the temporal location biases, we propose two anti-bias datasets with location distribution shifts, named Charades-STA-Len and Charades-STA-Mom. The experimental results demonstrate that our efficient framework consistently outperforms state-of-the-art methods on three public benchmarks, and exhibits better generalization and robustness on the proposed anti-bias datasets. The code, model, and anti-bias evaluation datasets are available at https://github.com/IMCCretrieval/MomentDiff., Comment: 19 pages, 6 figures

Probabilistic graphical models play a crucial role in machine learning and have wide applications in various fields. One pivotal subset is undirected graphical models, also known as Markov random fields. In this work, we investigate the structure learning methods of Markov random fields on quantum computers. We propose a quantum algorithm for structure learning of an $r$-wise Markov Random Field with a bounded degree underlying graph, based on a nearly optimal classical greedy algorithm. The quantum algorithm provides a polynomial speed-up over the classical counterpart in terms of the number of variables. Our work demonstrates the potential merits of quantum computation over classical computation in solving some problems in machine learning., Comment: 10 pages, 1 figure

Markov random fields (MRFs) appear in many problems in machine learning and statistics. From a computational learning theory point of view, a natural problem of learning MRFs arises: given samples from an MRF from a restricted class, learn the structure of the MRF, that is the neighbors of each node of the underlying graph. In this work, we start at a known near-optimal classical algorithm for this learning problem and develop a modified classical algorithm. This classical algorithm retains the run time and guarantee of the previous algorithm and enables the use of quantum subroutines. Adapting a previous quantum algorithm, the Quantum Sparsitron, we provide a polynomial quantum speedup in terms of the number of variables for learning the structure of an MRF, if the MRF has bounded degree., Comment: 35 pages

The solving of linear systems provides a rich area to investigate the use of nearer-term, noisy, intermediate-scale quantum computers. In this work, we discuss hybrid quantum-classical algorithms for skewed linear systems for over-determined and under-determined cases. Our input model is such that the columns or rows of the matrix defining the linear system are given via quantum circuits of poly-logarithmic depth and the number of circuits is much smaller than their Hilbert space dimension. Our algorithms have poly-logarithmic dependence on the dimension and polynomial dependence in other natural quantities. In addition, we present an algorithm for the special case of a factorized linear system with run time poly-logarithmic in the respective dimensions. At the core of these algorithms is the Hadamard test and in the second part of this paper we consider the optimization of the circuit depth of this test. Given an $n$-qubit and $d$-depth quantum circuit $\mathcal{C}$, we can approximate $\langle 0|\mathcal{C}|0\rangle$ using $(n + s)$ qubits and $O\left(\log s + d\log (n/s) + d\right)$-depth quantum circuits, where $s\leq n$. In comparison, the standard implementation requires $n+1$ qubits and $O(dn)$ depth. Lattice geometries underlie recent quantum supremacy experiments with superconducting devices. We also optimize the Hadamard test for an $(l_1\times l_2)$ lattice with $l_1 \times l_2 = n$, and can approximate $\langle 0|\mathcal{C} |0\rangle$ with $(n + 1)$ qubits and $O\left(d \left(l_1 + l_2\right)\right)$-depth circuits. In comparison, the standard depth is $O\left(d n^2\right)$ in this setting. Both of our optimization methods are asymptotically tight in the case of one-depth quantum circuits $\mathcal{C}$., Comment: 28+16 pages, 6 figures

In many real-world datasets, like WebVision, the performance of DNN based classifier is often limited by the noisy labeled data. To tackle this problem, some image related side information, such as captions and tags, often reveal underlying relationships across images. In this paper, we present an efficient weakly supervised learning by using a Side Information Network (SINet), which aims to effectively carry out a large scale classification with severely noisy labels. The proposed SINet consists of a visual prototype module and a noise weighting module. The visual prototype module is designed to generate a compact representation for each category by introducing the side information. The noise weighting module aims to estimate the correctness of each noisy image and produce a confidence score for image ranking during the training procedure. The propsed SINet can largely alleviate the negative impact of noisy image labels, and is beneficial to train a high performance CNN based classifier. Besides, we released a fine-grained product dataset called AliProducts, which contains more than 2.5 million noisy web images crawled from the internet by using queries generated from 50,000 fine-grained semantic classes. Extensive experiments on several popular benchmarks (i.e. Webvision, ImageNet and Clothing-1M) and our proposed AliProducts achieve state-of-the-art performance. The SINet has won the first place in the classification task on WebVision Challenge 2019, and outperformed other competitors by a large margin., Comment: Accepted by ECCV 2020

In this article, we will derive the differential equations considering the concentration polarization (\textsc{cp}) in membrane separations and purifications, which involve convective-diffusive equations of the concentration polarization layer and the Spiegler-Kedem-Katchalsky (\textsc{skk}) model of the membrane layer. Analytical solutions of these differential equations are straightforward and given. The film theory coupled \textsc{skk} model can be used to evaluate the degree of concentration polarization, and predict flux and rejection rates., Comment: There is an error in Eq. (8) on the page 8

Prominent features of simulated moving bed (SMB) chromatography processes in the downstream processing is based on the determination of operating conditions. However, effects of different types of uncertainties have to be studied and analysed whenever the triangle theory or numerical optimization approaches are applied. In this study, a Bayesian inference based method is introduced to consider the uncertainty of operating conditions on the performance assessment, of a glucose-fructose SMB unit under linear condition. A multiple chain Markov Chain Monte Carlo (MCMC) algorithm (i.e., Metropolis algorithm with delayed rejection and adjusted Metropolis) is applied to generate samples. The proposed method renders versatile information by constructing from the MCMC samples, e.g., posterior distributions, uncertainties, credible intervals of the operating conditions, and posterior predictive check and Pareto fronts between each pair of the performance indicators. Additionally, the MCMC samples can be mapped onto the $(m_\text{II}, m_\text{III})$ and $(m_\text{IV}, m_\text{I})$ plains to show the actually complete separation region under uncertainties. The proposed method is a convenient tool to find both optimal values and uncertainties of the operating conditions. Moreover, it is not limited to SMB processes under the linear isotherm; and it should be more powerful in the nonlinear scenarios., Comment: 32 pages, 8 figures, 4 tables

Model-based process design of ion-exchange simulated moving bed (IEX-SMB) chromatography for center-cut separation of proteins is studied. Use of nonlinear binding models that describe more accurate adsorption behaviours of macro-molecules could make it impossible to utilize triangle theory to obtain operating parameters. Moreover, triangle theory provides no rules to design salt profiles in IEX-SMB. In the modelling study here, proteins (i.e., ribonuclease, cytochrome and lysozyme) on the chromatographic columns packed with strong cation-exchanger SP Sepharose FF is used as an example system. The general rate model with steric mass-action kinetics was used; two closed-loop IEX-SMB network schemes were investigated (i.e., cascade and eight-zone schemes). Performance of the IEX-SMB schemes was examined with respect to multi-objective indicators (i.e., purity and yield) and productivity, and compared to a single column batch system with the same amount of resin utilized. A multi-objective sampling algorithm, Markov Chain Monte Carlo (MCMC), was used to generate samples for constructing the Pareto optimal fronts. MCMC serves on the sampling purpose, which is interested in sampling the Pareto optimal points as well as those near Pareto optimal. Pareto fronts of the three schemes provide the full information of trade-off between the conflicting indicators of purity and yield. The results indicate the cascade IEX-SMB scheme and the integrated eight-zone IEX-SMB scheme have the similar performance that both outperforms the single column batch system., Comment: 26 pages, 14 figures, 7 tables

Efficiently processing basic linear algebra subroutines is of great importance for a wide range of computational problems. In this paper, we consider techniques to implement matrix functions on a quantum computer, which are composed of basic matrix operations on a set of matrices. These matrix operations include addition, multiplication, Kronecker sum, tensor product, Hadamard product, and single-matrix functions. We discuss the composed matrix functions in terms of the estimation of scalar quantities such as inner products, trace, determinant and Schatten p-norms. We thus provide a framework for compiling instructions for linear algebraic computations into gate sequences on actual quantum computers.

In this work, we propose the first quantum Ans\"atze for the statistical relational learning on knowledge graphs using parametric quantum circuits. We introduce two types of variational quantum circuits for knowledge graph embedding. Inspired by the classical representation learning, we first consider latent features for entities as coefficients of quantum states, while predicates are characterized by parametric gates acting on the quantum states. For the first model, the quantum advantages disappear when it comes to the optimization of this model. Therefore, we introduce a second quantum circuit model where embeddings of entities are generated from parameterized quantum gates acting on the pure quantum state. The benefit of the second method is that the quantum embeddings can be trained efficiently meanwhile preserving the quantum advantages. We show the proposed methods can achieve comparable results to the state-of-the-art classical models, e.g., RESCAL, DistMult. Furthermore, after optimizing the models, the complexity of inductive inference on the knowledge graphs might be reduced with respect to the number of entities.

We investigate the performance of a quantum algorithm for solving classical 3-SAT problems. A cycle of post-selected measurements drives the computer's register monotonically toward a steady state which is correlated to the classical solution(s). An internal parameter $\theta$ determines both the degree of correlation and the success probability, thus controlling the algorithm's runtime. Optionally this parameter can be gradually evolved during the algorithm's execution to create a Zeno-like effect; this can be viewed as an adiabatic evolution of a Hamiltonian which remains frustration-free at all points, and we lower-bound the corresponding gap. In exact numerical simulations of small systems up to 34 qubits our approach competes favourably with a high-performing classical 3-SAT solver, which itself outperforms a brute-force application of Grover's search., Comment: 16 pages, 9 figs

In this paper, we address the problem of person re-identification, which refers to associating the persons captured from different cameras. We propose a simple yet effective human part-aligned representation for handling the body part misalignment problem. Our approach decomposes the human body into regions (parts) which are discriminative for person matching, accordingly computes the representations over the regions, and aggregates the similarities computed between the corresponding regions of a pair of probe and gallery images as the overall matching score. Our formulation, inspired by attention models, is a deep neural network modeling the three steps together, which is learnt through minimizing the triplet loss function without requiring body part labeling information. Unlike most existing deep learning algorithms that learn a global or spatial partition-based local representation, our approach performs human body partition, and thus is more robust to pose changes and various human spatial distributions in the person bounding box. Our approach shows state-of-the-art results over standard datasets, Market-$1501$, CUHK$03$, CUHK$01$ and VIPeR., Comment: Accepted by ICCV 2017

The adiabatic quantum algorithm has drawn intense interest as a potential approach to accelerating optimization tasks using quantum computation. The algorithm is most naturally realised in systems which support Hamiltonian evolution, rather than discrete gates. We explore an alternative approach in which slowly varying measurements are used to mimic adiabatic evolution. We show that for certain Hamiltonians, which remain frustration-free all along the adiabatic path, the necessary measurements can be implemented through the measurement of random terms from the Hamiltonian. This offers a new, and potentially more viable, method of realising adiabatic evolution in gate-based quantum computer architectures., Comment: 4 pages. Comments welcome

A (k,n)-threshold secret-sharing scheme allows for a string to be split into n shares in such a way that any subset of at least k shares suffices to recover the secret string, but such that any subset of at most k-1 shares contains no information about the secret. Quantum secret-sharing schemes extend this idea to the sharing of quantum states. Here we propose a method of performing computation on quantum shared secrets. We introduce a (n,n)-quantum secret sharing scheme together with a set of protocols that allow quantum circuits to be evaluated on the shared secret without the need to decode the secret. We consider a multipartite setting, with each participant holding a share of the secret. We show that if there exists at least one honest participant, no group of dishonest participants can recover any information about the shared secret, independent of their deviations from the protocol., Comment: 5 pages, 2 figures, 1 table

A deep residual network, built by stacking a sequence of residual blocks, is easy to train, because identity mappings skip residual branches and thus improve information flow. To further reduce the training difficulty, we present a simple network architecture, deep merge-and-run neural networks. The novelty lies in a modularized building block, merge-and-run block, which assembles residual branches in parallel through a merge-and-run mapping: Average the inputs of these residual branches (Merge), and add the average to the output of each residual branch as the input of the subsequent residual branch (Run), respectively. We show that the merge-and-run mapping is a linear idempotent function in which the transformation matrix is idempotent, and thus improves information flow, making training easy. In comparison to residual networks, our networks enjoy compelling advantages: they contain much shorter paths, and the width, i.e., the number of channels, is increased. We evaluate the performance on the standard recognition tasks. Our approach demonstrates consistent improvements over ResNets with the comparable setup, and achieves competitive results (e.g., $3.57\%$ testing error on CIFAR-$10$, $19.00\%$ on CIFAR-$100$, $1.51\%$ on SVHN).

A key problem in salient object detection is how to effectively model the semantic properties of salient objects in a data-driven manner. In this paper, we propose a multi-task deep saliency model based on a fully convolutional neural network (FCNN) with global input (whole raw images) and global output (whole saliency maps). In principle, the proposed saliency model takes a data-driven strategy for encoding the underlying saliency prior information, and then sets up a multi-task learning scheme for exploring the intrinsic correlations between saliency detection and semantic image segmentation. Through collaborative feature learning from such two correlated tasks, the shared fully convolutional layers produce effective features for object perception. Moreover, it is capable of capturing the semantic information on salient objects across different levels using the fully convolutional layers, which investigate the feature-sharing properties of salient object detection with great feature redundancy reduction. Finally, we present a graph Laplacian regularized nonlinear regression model for saliency refinement. Experimental results demonstrate the effectiveness of our approach in comparison with the state-of-the-art approaches., Comment: To appear in IEEE Transactions on Image Processing (TIP), Project Website: http://www.zhaoliming.net/research/deepsaliency

The connection between certain entangled states and graphs has been heavily studied in the context of measurement-based quantum computation as a tool for understanding entanglement. Here we show that this correspondence can be harnessed in the reverse direction to yield a graph data structure which allows for more efficient manipulation and comparison of graphs than any possible classical structure. We introduce efficient algorithms for many transformation and comparison operations on graphs represented as graph states, and prove that no classical data structure can have similar performance for the full set of operations studied., Comment: 9 pages, 1 figure. Comments welcome

As an important and challenging problem in computer vision and graphics, keypoint-based object tracking is typically formulated in a spatio-temporal statistical learning framework. However, most existing keypoint trackers are incapable of effectively modeling and balancing the following three aspects in a simultaneous manner: temporal model coherence across frames, spatial model consistency within frames, and discriminative feature construction. To address this issue, we propose a robust keypoint tracker based on spatio-temporal multi-task structured output optimization driven by discriminative metric learning. Consequently, temporal model coherence is characterized by multi-task structured keypoint model learning over several adjacent frames, while spatial model consistency is modeled by solving a geometric verification based structured learning problem. Discriminative feature construction is enabled by metric learning to ensure the intra-class compactness and inter-class separability. Finally, the above three modules are simultaneously optimized in a joint learning scheme. Experimental results have demonstrated the effectiveness of our tracker., Comment: Accepted by AAAI-15

We define genuine total, classical and quantum correlations in tripartite systems. The measure we propose is based on the idea that genuine tripartite correlation exists if and only if the correlation between any bipartition does not vanish. We find in a symmetrical tripartite state, for total correlation and classical correlation, the genuine tripartite correlations are no less than pair-wise correlations. However, the genuine quantum tripartite correlation can be surpassed by the pair-wise quantum correlations. Analytical expressions for genuine tripartite correlations are obtained for pure states and rank-2 symmetrical states. The genuine correlations in both entangled and separable states are calculated., Comment: 5 pages, 3 figures