Author name cluster

Xiaodi Wu 0001

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

1 author row

ICML Conference 2023 Conference Paper

Analyzing Convergence in Quantum Neural Networks: Deviations from Neural Tangent Kernels

Xuchen You
Shouvanik Chakrabarti
Boyang Chen
Xiaodi Wu 0001

A quantum neural network (QNN) is a parameterized mapping efficiently implementable on near-term Noisy Intermediate-Scale Quantum (NISQ) computers. It can be used for supervised learning when combined with classical gradient-based optimizers. Despite the existing empirical and theoretical investigations, the convergence of QNN training is not fully understood. Inspired by the success of the neural tangent kernels (NTKs) in probing into the dynamics of classical neural networks, a recent line of works proposes to study over-parameterized QNNs by examining a quantum version of tangent kernels. In this work, we study the dynamics of QNNs and show that contrary to popular belief it is qualitatively different from that of any kernel regression: due to the unitarity of quantum operations, there is a non-negligible deviation from the tangent kernel regression derived at the random initialization. As a result of the deviation, we prove the at-most sublinear convergence for QNNs with Pauli measurements, which is beyond the explanatory power of any kernel regression dynamics. We then present the actual dynamics of QNNs in the limit of over-parameterization. The new dynamics capture the change of convergence rate during training and implies that the range of measurements is crucial to the fast QNN convergence.

Details

ICML Conference 2021 Conference Paper

Exponentially Many Local Minima in Quantum Neural Networks

Xuchen You
Xiaodi Wu 0001

Quantum Neural Networks (QNNs), or the so-called variational quantum circuits, are important quantum applications both because of their similar promises as classical neural networks and because of the feasibility of their implementation on near-term intermediate-size noisy quantum machines (NISQ). However, the training task of QNNs is challenging and much less understood. We conduct a quantitative investigation on the landscape of loss functions of QNNs and identify a class of simple yet extremely hard QNN instances for training. Specifically, we show for typical under-parameterized QNNs, there exists a dataset that induces a loss function with the number of spurious local minima depending exponentially on the number of parameters. Moreover, we show the optimality of our construction by providing an almost matching upper bound on such dependence. While local minima in classical neural networks are due to non-linear activations, in quantum neural networks local minima appear as a result of the quantum interference phenomenon. Finally, we empirically confirm that our constructions can indeed be hard instances in practice with typical gradient-based optimizers, which demonstrates the practical value of our findings.

Details

ICML Conference 2019 Conference Paper

Sublinear quantum algorithms for training linear and kernel-based classifiers

Tongyang Li
Shouvanik Chakrabarti
Xiaodi Wu 0001

We investigate quantum algorithms for classification, a fundamental problem in machine learning, with provable guarantees. Given $n$ $d$-dimensional data points, the state-of-the-art (and optimal) classical algorithm for training classifiers with constant margin by Clarkson et al. runs in $\tilde{O}(n +d)$, which is also optimal in its input/output model. We design sublinear quantum algorithms for the same task running in $\tilde{O}(\sqrt{n} +\sqrt{d})$, a quadratic improvement in both $n$ and $d$. Moreover, our algorithms use the standard quantization of the classical input and generate the same classical output, suggesting minimal overheads when used as subroutines for end-to-end applications. We also demonstrate a tight lower bound (up to poly-log factors) and discuss the possibility of implementation on near-term quantum machines.

Details

STOC Conference 2016 Conference Paper

Sample-optimal tomography of quantum states

Jeongwan Haah
Aram W. Harrow
Zhengfeng Ji
Xiaodi Wu 0001
Nengkun Yu

It is a fundamental problem to decide how many copies of an unknown mixed quantum state are necessary and sufficient to determine the state. This is the quantum analogue of the problem of estimating a probability distribution given some number of samples. Previously, it was known only that estimating states to error є in trace distance required O ( dr 2 /є 2 ) copies for a d -dimensional density matrix of rank r . Here, we give a measurement scheme (POVM) that uses O ( ( dr / δ ) ln( d /δ) ) copies to estimate ρ to error δ in infidelity. This implies O ( ( dr / є 2 )· ln( d /є) ) copies suffice to achieve error є in trace distance. For fixed d , our measurement can be implemented on a quantum computer in time polynomial in n . We also use the Holevo bound from quantum information theory to prove a lower bound of Ω( dr /є 2 )/ log( d / r є) copies needed to achieve error є in trace distance. This implies a lower bound Ω( dr /δ)/log( d / r δ) for the estimation error δ in infidelity. These match our upper bounds up to log factors. Our techniques can also show an Ω( r 2 d /δ) lower bound for measurement strategies in which each copy is measured individually and then the outcomes are classically post-processed to produce an estimate. This matches the known achievability results and proves for the first time that such “product” measurements have asymptotically suboptimal scaling with d and r .

Details