Search

In 1948, Fritz John proposed a theorem stating that every convex body has a unique maximal volume inscribed ellipsoid, known as the John ellipsoid. The John ellipsoid has become fundamental in mathematics, with extensive applications in high-dimensional sampling, linear programming, and machine learning. Designing faster algorithms to compute the John ellipsoid is therefore an important and emerging problem. In [Cohen, Cousins, Lee, Yang COLT 2019], they established an algorithm for approximating the John ellipsoid for a symmetric convex polytope defined by a matrix $A \in \mathbb{R}^{n \times d}$ with a time complexity of $O(nd^2)$. This was later improved to $O(\text{nnz}(A) + d^\omega)$ by [Song, Yang, Yang, Zhou 2022], where $\text{nnz}(A)$ is the number of nonzero entries of $A$ and $\omega$ is the matrix multiplication exponent. Currently $\omega \approx 2.371$ [Alman, Duan, Williams, Xu, Xu, Zhou 2024]. In this work, we present the first quantum algorithm that computes the John ellipsoid utilizing recent advances in quantum algorithms for spectral approximation and leverage score approximation, running in $O(\sqrt{n}d^{1.5} + d^\omega)$ time. In the tall matrix regime, our algorithm achieves quadratic speedup, resulting in a sublinear running time and significantly outperforming the current best classical algorithms.

Determining the John ellipsoid - the largest volume ellipsoid contained within a convex polytope - is a fundamental problem with applications in machine learning, optimization, and data analytics. Recent work has developed fast algorithms for approximating the John ellipsoid using sketching and leverage score sampling techniques. However, these algorithms do not provide privacy guarantees for sensitive input data. In this paper, we present the first differentially private algorithm for fast John ellipsoid computation. Our method integrates noise perturbation with sketching and leverage score sampling to achieve both efficiency and privacy. We prove that (1) our algorithm provides $(\epsilon,\delta)$-differential privacy, and the privacy guarantee holds for neighboring datasets that are $\epsilon_0$-close, allowing flexibility in the privacy definition; (2) our algorithm still converges to a $(1+\xi)$-approximation of the optimal John ellipsoid in $O(\xi^{-2}(\log(n/\delta_0) + (L\epsilon_0)^{-2}))$ iterations where $n$ is the number of data point, $L$ is the Lipschitz constant, $\delta_0$ is the failure probability, and $\epsilon_0$ is the closeness of neighboring input datasets. Our theoretical analysis demonstrates the algorithm's convergence and privacy properties, providing a robust approach for balancing utility and privacy in John ellipsoid computation. This is the first differentially private algorithm for fast John ellipsoid computation, opening avenues for future research in privacy-preserving optimization techniques.

We study the existence and multiplicity of positive solutions with prescribed $L^2$-norm for the Sobolev critical Schr\"odinger equation on a bounded domain $\Omega\subset\mathbb{R}^N$, $N\ge3$: \[ -\Delta U = \lambda U + U^{2^{*}-1},\qquad U\in H^1_0(\Omega),\qquad \int_\Omega U^2\,dx = \rho^{2}, \] where $2^*=\frac{2N}{N-2}$. First, we consider a general bounded domain $\Omega$ in dimension $N\ge3$, with a restriction, only in dimension $N=3$, involving its inradius and first Dirichlet eigenvalue. In this general case we show the existence of a mountain pass solution on the $L^2$-sphere, for $\rho$ belonging to a subset of positive measure of the interval $(0,\rho^{**})$, for a suitable threshold $\rho^{**}>0$. Next, assuming that $\Omega$ is star-shaped, we extend the previous result to all values $\rho\in(0,\rho^{**})$. With respect to that of local minimizers, already known in the literature, the existence of mountain pass solutions in the Sobolev critical case is much more elusive. In particular, our proofs are based on the sharp analysis of the bounded Palais-Smale sequences, provided by a nonstandard adaptation of the Struwe monotonicity trick, that we develop., Comment: 24 pages

Recent technological advancements show promise in leveraging quantum mechanical phenomena for computation. This brings substantial speed-ups to problems that are once considered to be intractable in the classical world. However, the physical realization of quantum computers is still far away from us, and a majority of research work is done using quantum simulators running on classical computers. Classical computers face a critical obstacle in simulating quantum algorithms. Quantum states reside in a Hilbert space whose size grows exponentially to the number of subsystems, i.e., qubits. As a result, the straightforward statevector approach does not scale due to the exponential growth of the memory requirement. Decision diagrams have gained attention in recent years for representing quantum states and operations in quantum simulations. The main advantage of this approach is its ability to exploit redundancy. However, mainstream quantum simulators still rely on statevectors or tensor networks. We consider the absence of decision diagrams due to the lack of parallelization strategies. This work explores several strategies for parallelizing decision diagram operations, specifically for quantum simulations. We propose optimal parallelization strategies. Based on the experiment results, our parallelization strategy achieves a 2-3 times faster simulation of Grover's algorithm and random circuits than the state-of-the-art single-thread DD-based simulator DDSIM.

In this paper, we study the existence of normalized solutions to the following nonlinear Choquard equation with exponential growth \begin{align*} \left\{ \begin{aligned} &-\Delta u+\lambda u=(I_{\alpha}\ast F(u))f(u), \quad \quad \hbox{in }\mathbb{R}^{2},\\ &\int_{\mathbb{R}^{2}}|u|^{2}dx=a^{2}, \end{aligned} \right. \end{align*} where $a>0$ is prescribed, $\lambda\in \mathbb{R}$, $\alpha\in(0,2)$, $I_{\alpha}$ denotes the Riesz potential, $\ast$ indicates the convolution operator, the function $f(t)$ has exponential growth in $\mathbb{R}^{2}$ and $F(t)=\int^{t}_{0}f(\tau)d\tau$. Using the Pohozaev manifold and variational methods, we establish the existence of normalized solutions to the above problem., Comment: arXiv admin note: text overlap with arXiv:2210.02331. text overlap with arXiv:2102.03001 by other authors

In this paper, we study the existence of normalized solutions to the following nonlinear Schr\"{o}dinger systems with exponential growth \begin{align*} \left\{ \begin{aligned} &-\Delta u+\lambda_{1}u=H_{u}(u,v), \quad \quad \hbox{in }\mathbb{R}^{2},\\ &-\Delta v+\lambda_{2} v=H_{v}(u,v), \quad \quad \hbox{in }\mathbb{R}^{2},\\ &\int_{\mathbb{R}^{2}}|u|^{2}dx=a^{2},\quad \int_{\mathbb{R}^{2}}|v|^{2}dx=b^{2}, \end{aligned} \right. \end{align*} where $a,b>0$ are prescribed, $\lambda_{1},\lambda_{2}\in \mathbb{R}$ and the functions $H_{u},H_{v}$ are partial derivatives of a Carath\'{e}odory function $H$ with $H_{u},H_{v}$ have exponential growth in $\mathbb{R}^{2}$. Our main results are totally new for Schr\"{o}dinger systems in $\mathbb{R}^{2}$. Using the Pohozaev manifold and variational methods, we establish the existence of normalized solutions to the above problem., Comment: arXiv admin note: text overlap with arXiv:2102.03001 by other authors

In this paper, we study the following class of fractional Hamiltonian systems: \begin{eqnarray*} \begin{aligned}\displaystyle \left\{ \arraycolsep=1.5pt \begin{array}{ll} (-\Delta)^{\frac{1}{2}} u + u = \Big(I_{\mu_{1}}\ast G(v)\Big)g(v) \ \ \ & \mbox{in} \ \mathbb{R},\\[2mm] (-\Delta)^{\frac{1}{2}} v + v = \Big(I_{\mu_{2}}\ast F(u)\Big)f(u) \ \ \ & \mbox{in} \ \mathbb{R}, \end{array} \right. \end{aligned} \end{eqnarray*} where $(-\Delta)^{\frac{1}{2}}$ is the square root Laplacian operator, $\mu_{1},\mu_{2}\in(0,1)$, $I_{\mu_{1}},I_{\mu_{2}}$ denote the Riesz potential, $\ast$ indicates the convolution operator, $F(s),G(s)$ are the primitive of $f(s),g(s)$ with $f(s),g(s)$ have exponential growth in $\mathbb{R}$. Using the linking theorem and variational methods, we establish the existence of at least one positive solution to the above problem., Comment: arXiv admin note: substantial text overlap with arXiv:2206.12086

In this paper, we study the following Hamiltonian Choquard-type elliptic systems involving singular weights \begin{eqnarray*} \begin{aligned}\displaystyle \left\{ \arraycolsep=1.5pt \begin{array}{ll} -\Delta u + V(x)u = \Big(I_{\mu_{1}}\ast \frac{G(v)}{|x|^{\alpha}}\Big)\frac{g(v)}{|x|^{\alpha}} \ \ \ & \mbox{in} \ \mathbb{R}^{2},\\[2mm] -\Delta v + V(x)v = \Big(I_{\mu_{2}}\ast \frac{F(u)}{|x|^{\beta}}\Big)\frac{f(u)}{|x|^{\beta}} \ \ \ & \mbox{in} \ \mathbb{R}^{2}, \end{array} \right. \end{aligned} \end{eqnarray*} where $\mu_{1},\mu_{2}\in(0,2)$, $0<\alpha \leq \frac{\mu_{1}}{2}$, $0<\beta \leq \frac{\mu_{2}}{2}$, $V(x)$ is a continuous positive potential, $I_{\mu_{1}}$ and $I_{\mu_{2}}$ denote the Riesz potential, $\ast$ indicates the convolution operator, $F(s),G(s)$ are the primitive of $f(s),g(s)$ with $f(s),g(s)$ have exponential growth in $\mathbb{R}^{2}$. Using the linking theorem and variational methods, we establish the existence of solutions to the above problem.