共找到 20 条结果
We extend the Geometric Refinement Transform (GRT) by introducing centroidal Voronoi tessellations (CVTs) into the refinement process, enhancing symmetry, reconstruction accuracy, and numerical stability. By applying Lloyds algorithm at each refinement level, we minimize centroidal energy and generate Voronoi regions that better align with the functions underlying structure. This approach reduces geometric distortion, suppresses reconstruction error, and provides a natural framework for adaptive refinement. We analyze convergence properties, quantify the reduction in reconstruction error using Taylor-based estimates and Lipschitz continuous functions, and propose perturbation strategies to escape symmetry-preserving local minima. The resulting transform offers improved accuracy for applications in medical imaging, signal processing, and physics simulations, while preserving the theoretical completeness and stability guarantees of the original GRT framework.
Lloyd algorithm is the standard iterative method for computing quantizers and codebooks in source coding and vector quantization. In this article, we study the dynamical and stability properties of the Lloyd map on the unit circle $\mathbb S^1$ using von Mises distributions. We construct the Lloyd iteration as a discrete dynamical system on the configuration space of ordered point sets modulo rotational symmetry. Also, we study the rotational equivarience of the Lloyd map. Further, we derive an explicit representation of the Jacobian matrix and prove that it possesses a circulant structure for the equally spaced configuration. Also, we study the bifurcation characteristics based on Lloyd map analysis. In the end, we provide the numerical algorithms for stability diagrams, Lyapunov spectrum estimation, and residue analysis, purely for empirical visualization. Our results provide a dynamical systems framework for Lloyd quantization on $\mathbb S^1$ for studying stability properties.
In this paper, we analyze the classical $K$-means alternating-minimization algorithm, also known as Lloyd's algorithm (Lloyd, 1956), for a mixture of Gaussians in a data-distributed setting that incorporates local iteration steps. Assuming unlabeled data distributed across multiple machines, we propose an algorithm, LocalKMeans, that performs Lloyd's algorithm in parallel in the machines by running its iterations on local data, synchronizing only every $L$ of such local steps. We characterize the cost of these local iterations against the non-distributed setting, and show that the price paid for the local steps is a higher required signal-to-noise ratio. While local iterations were theoretically studied in the past for gradient-based learning methods, the analysis of unsupervised learning methods is more involved owing to the presence of latent variables, e.g. cluster identities, than that of an iterative gradient-based algorithm. To obtain our results, we adapt a virtual iterate method to work with a non-convex, non-smooth objective function, in conjunction with a tight statistical analysis of Lloyd steps.
We propose a novel quantum algorithm for solving nuclear resonances, which is based on the iterative Harrow-Hassidim-Lloyd algorithm and eigenvector continuation with complex scaling. To validate this approach, we compute the resonant states of $α-α$ system and achieve results in good agreement with traditional methods. Our study offers a new perspective on calculating eigenvalues of non-Hermitian operators and lays some groundwork for further exploration of nuclear resonances using quantum computing.
By using the quantum computing the properties of hypernuclei ${}^5_Λ$He, ${}^{\ 6}_{ΛΛ}$He and ${}^9_Λ$Be can be investigated within microscopic cluster model. Our approach combines quantum neural network (QNN) with iterative Harrow-Hassidim-Lloyd (IHHL) algorithm (abbreviated as QNN-IHHL) to solve the quantum many-body problem. To efficiently describe resonance phenomena, we employ complex scaling and eigenvector continuation techniques, providing a robust framework for identifying few-cluster resonance parameters within quantum computing. To validate our quantum algorithm, the resonant $4^{+}$ state of ${}^9_Λ$Be is chosen as a core example. With QNN-IHHL algorithm we realize a fully quantum workflow, which provides a novel framework and some ground work for exploring resonance properties in complex nuclear many-body systems.
In [\href{https://quantum-journal.org/papers/q-2022-12-07-872/}{Quantum 6, 872, 2022}], Linden and de Wolf proposed a lightweight protocol for verifying the average-case correct behavior of the quantum Fourier transform (QFT). They proved that good average-case QFT performance suffices for good worst-case performance in several quantum tasks. Here we provide another application of this worst-case-to-average-case reduction, using a strengthened Linden-de Wolf protocol. We show that, across three distinct scenarios, the Harrow-Hassidim-Lloyd algorithm can be executed with provably good worst-case performance, assuming only that the QFT is correct on average.
We extend the Harrow-Hassidim-Lloyd (HHL) algorithm, which is well-studied in the qubit framework, to its qutrit counterpart (which we call qutrit HHL, as opposed to qubit HHL, which is HHL using qubits), and develop a program for its implementation. We design Weyl-Heisenberg gadgets, the qutrit equivalents of Pauli gadgets, and come up with a practical implementation scheme for qutrit HHL. We test HHL with qutrits for simple matrices and verify the results against the expected outcomes. We apply the algorithm to quantum chemistry, and in particular, to the potential energy curve calculations of the model problem of the Hydrogen molecule in the split valence basis. We do so for two cases: 1-qutrit and 2-qutrit input states, where the latter makes use of our gadgets. We compare the number of qudits and the number of gates required between qubit and qutrit HHL implementations. In general, we find that for a fixed precision, the qutrit HHL circuit requires fewer number of qudits and comparable number of two-qudit gates than its qubit counterpart.
Although the Harrow-Hassidim-Lloyd (HHL) algorithm offers an exponential speedup in system size for treating linear equations of the form $A\vec{x}=\vec{b}$ on quantum computers when compared to their traditional counterparts, it faces a challenge related to the condition number ($\mathcalκ$) scaling of the $A$ matrix. In this work, we address the issue by introducing the post-selection-improved HHL (Psi-HHL) framework that operates on a simple yet effective premise: subtracting mixed and wrong signals to extract correct signals while providing the benefit of optimal scaling in the condition number of $A$ (denoted as $\mathcalκ$) for large $\mathcalκ$ scenarios. This approach, which leads to minimal increase in circuit depth, has the important practical implication of having to use substantially fewer shots relative to the traditional HHL algorithm. The term `signal' refers to a feature of $|x\rangle$. We design circuits for overlap and expectation value estimation in the Psi-HHL framework. We demonstrate performance of Psi-HHL via numerical simulations. We carry out two sets of computations, where we go up to 26-qubit calculations, to demonstrate the ability of Psi-HHL to handle s
We introduce two variations of the quantum phase estimation algorithm: quantum shifted phase estimation and quantum punctured phase estimation. The shifted method employs a bit-string left shift to discard the most significant bit and focus on lower-order phase components, and the punctured method removes qubits corresponding to known phase bits, thereby streamlining the circuit. To demonstrate the effectiveness of the two variations, we integrate them into a hybrid quantum-classical implementation of the Harrow--Hassidim--Lloyd algorithm for solving linear systems. The hybrid method leverages both quantum and classical processors to identify and remove unnecessary qubits and gates. As a result, our method reduces qubit and gate counts compared to previous implementations, leading to lower overall circuit error rates on current hardware. Experimental demonstrations on IBM superconducting hardware confirm the error-mitigation effectiveness of the proposed hybrid method.
The development of quantum processors capable of handling practical fluid flow problems represents a distant yet promising frontier. Recent strides in quantum algorithms, particularly linear solvers, have illuminated the path toward quantum solutions for classical fluid flow solvers. However, assessing the capability of these quantum linear systems algorithms (QLSAs) in solving ideal flow equations on real hardware is crucial for their future development in practical fluid flow applications. In this study, we examine the capability of a canonical QLSA, the Harrow-Hassidim-Lloyd (HHL) algorithm, in accurately solving the system of linear equations governing an idealized fluid flow problem, specifically the Hele-Shaw flow. Our investigation focuses on analyzing the accuracy and computational cost of the HHL solver. To gauge the stability and convergence of the solver, we conduct shots-based simulations on quantum simulators. Furthermore, we share insights gained from executing the HHL solver on superconducting quantum devices. To mitigate errors arising from qubit measurement, gate operations, and qubit decoherence inherent in quantum devices, we employ various error suppression and
Lloyd's algorithm is an iterative method that solves the quantization problem, i.e. the approximation of a target probability measure by a discrete one, and is particularly used in digital applications. This algorithm can be interpreted as a gradient method on a certain quantization functional which is given by optimal transport. We study the sequential convergence (to a single accumulation point) for two variants of Lloyd's method: (i) optimal quantization with an arbitrary discrete measure and (ii) uniform quantization with a uniform discrete measure. For both cases, we prove sequential convergence of the iterates under an analiticity assumption on the density of the target measure. This includes for example analytic densities truncated to a compact semi-algebraic set. The argument leverages the log analytic nature of globally subanalytic integrals, the interpretation of Lloyd's method as a gradient method and the convergence analysis of gradient algorithms under Kurdyka-Lojasiewicz assumptions. As a by-product, we also obtain definability results for more general semi-discrete optimal transport losses such as transport distances with general costs, the max-sliced Wasserstein dis
Clustering is a commonplace problem in many areas of data science, with applications in biology and bioinformatics, understanding chemical structure, image segmentation, building recommender systems, and many more fields. While there are many different clustering variants (based on given distance or graph structure, probability distributions, or data density), we consider here the problem of clustering nodes in a graph, motivated by the problem of aggregating discrete degrees of freedom in multigrid and domain decomposition methods for solving sparse linear systems. Specifically, we consider the challenge of forming balanced clusters in the graph of a sparse matrix for use in algebraic multigrid, although the algorithm has general applicability. Based on an extension of the Bellman-Ford algorithm, we generalize Lloyd's algorithm for partitioning subsets of Rn to balance the number of nodes in each cluster; this is accompanied by a rebalancing algorithm that reduces the overall energy in the system. The algorithm provides control over the number of clusters and leads to "well centered" partitions of the graph. Theoretical results are provided to establish linear complexity and numer
In the context of unsupervised learning, Lloyd's algorithm is one of the most widely used clustering algorithms. It has inspired a plethora of work investigating the correctness of the algorithm under various settings with ground truth clusters. In particular, in 2016, Lu and Zhou have shown that the mis-clustering rate of Lloyd's algorithm on $n$ independent samples from a sub-Gaussian mixture is exponentially bounded after $O(\log(n))$ iterations, assuming proper initialization of the algorithm. However, in many applications, the true samples are unobserved and need to be learned from the data via pre-processing pipelines such as spectral methods on appropriate data matrices. We show that the mis-clustering rate of Lloyd's algorithm on perturbed samples from a sub-Gaussian mixture is also exponentially bounded after $O(\log(n))$ iterations under the assumptions of proper initialization and that the perturbation is small relative to the sub-Gaussian noise. In canonical settings with ground truth clusters, we derive bounds for algorithms such as $k$-means$++$ to find good initializations and thus leading to the correctness of clustering via the main result. We show the implications
We explore the complexity equals volume proposal for planar black holes in anti-de Sitter (AdS) spacetime in 2+1 dimensions, with an end of the world (ETW) brane behind the horizon. We allow for the possibility of intrinsic gravitational dynamics in the form of Jackiw-Teitelboim (JT) gravity to be localized on the brane. We compute the asymptotic rate of change of volume complexity analytically and obtain the full time dependence using numerical techniques. We find that the inclusion of JT gravity on the brane leads to interesting effects on time dependence of holographic complexity. We identify the region in parameter space (the brane location and the JT coupling) for which the rate of change of complexity violates the Lloyd bound. In an equivalent description of the model in terms of an asymptotically AdS wormhole, we connect the violation of the Lloyd bound to the violation of a suitable energy condition in the bulk that we introduce. We also compare the Lloyd bound constraints to previously derived constraints on the bulk parameters in this model that are based on bounds on entanglement growth in the dual CFT state.
The neutron optical Lloyd interferometer can serve as a potent experiment for probing fundamental physics beyond the standard models of particles and cosmology. In this article, we provide a full Green's function analysis of a Lloyd interferometer in the limit that the reflecting mirror extends to the screen. We consider two distinct situations: first, we will review the theoretical case of no external fields being present. Subsequently, we will analyze the case in which a gravitational field is acting on the neutrons. The latter case provides the theory necessary for using a Lloyd interferometer as a probe of gravitational fields.
Quantum algorithms have the ability to reduce runtime for executing tasks beyond the capabilities of classical algorithms. Therefore, identifying the resources responsible for quantum advantages is an interesting endeavour. We prove that nonvanishing quantum correlations, both bipartite and genuine multipartite entanglement, are required for solving nontrivial linear systems of equations in the Harrow-Hassidim-Lloyd (HHL) algorithm. Moreover, we find a nonvanishing l1-norm quantum coherence of the entire system and the register qubit which turns out to be related to the success probability of the algorithm. Quantitative analysis of the quantum resources reveals that while a significant amount of bipartite entanglement is generated in each step and required for this algorithm, multipartite entanglement content is inversely proportional to the performance indicator. In addition, we report that when imperfections chosen from Gaussian distribution are incorporated in controlled rotations, multipartite entanglement increases with the strength of the disorder, albeit error also increases while bipartite entanglement and coherence decreases, confirming the beneficial role of bipartite ent
This research presents a novel Discrete Event Simulation (DES) of the Lloyd's of London specialty insurance market, exploring complex market dynamics that have not been previously studied quantitatively. The proof-of-concept model allows for the simulation of various scenarios that capture important market phenomena such as the underwriting cycle, the impact of risk syndication, and the importance of appropriate exposure management. Despite minimal calibration, our model has shown that it is a valuable tool for understanding and analysing the Lloyd's of London specialty insurance market, particularly in terms of identifying areas for further investigation for regulators and participants of the market alike. The results generate the expected behaviours that, syndicates (insurers) are less likely to go insolvent if they adopt sophisticated exposure management practices, catastrophe events lead to more defined patterns of cyclicality and cause syndicates to substantially increase their premiums offered. Lastly, syndication enhances the accuracy of actuarial price estimates and narrows the divergence among syndicates. Overall, this research offers a new perspective on the Lloyd's of Lo
This paper presents a distributed rule-based Lloyd algorithm (RBL) for multi-robot motion planning and control. The main limitations of the basic Loyd-based algorithm (LB) concern deadlock issues and the failure to address dynamic constraints effectively. Our contribution is twofold. First, we show how RBL is able to provide safety and convergence to the goal region without relying on communication between robots, nor synchronization between the robots. We considered different dynamic constraints with control inputs saturation. Second, we show that the Lloyd-based algorithm (without rules) can be successfully used as a safety layer for learning-based approaches, leading to non-negligible benefits. We further prove the soundness, reliability, and scalability of RBL through extensive simulations, comparisons with the state of the art, and experimental validations on small-scale car-like robots, unicycle-like robots, omnidirectional robots, and aerial robots on the field.
The Harrow-Hassidim-Lloyd quantum algorithm was proposed to solve linear systems of equations $A\vec{x} = \vec{b}$ and it is the core of various applications. However, there is not an explicit quantum circuit for the subroutine which maps the inverse of the problem matrix $A$ into an ancillary qubit. This makes challenging the implementation in current quantum devices, forcing us to use hybrid approaches. Here, we propose a systematic manner to implement this subroutine, which can be adapted to other functions $f(A)$ of the matrix $A$, we present a co-designed quantum processor which reduces the depth of the algorithm, and we introduce its digital-analog implementation. The depth of our proposal scales with the precision $ε$ as $\mathcal{O}(ε^{-1})$, which is bounded by the number of samples allowed for a certain experiment. The co-design of the Harrow-Hassidim-Lloyd algorithm leads to a "kite-like" architecture, which allows us to reduce the number of required SWAP gates. Finally, merging a co-design quantum processor architecture with a digital-analog implementation contributes to the reduction of noise sources during the experimental realization of the algorithm.
It has been discussed recently how quantum illumination can be used to increase the accuracy of the value range-delay measurement \cite{Zhuang Shapiro 2022} in the domain of SNR compatible with current radar systems. However, the advantage described in [1] requires of a large integration time. In this work it is argued that multiple entangled photon quantum illumination could help to reduce the integration time when evaluating range-delay. Our analysis is performed in the framework of three entangled photon states discrete quantum illumination protocols. In this setting it is shown explicitly that using a direct generalization of Lloyd's protocol to the case where signal states describe two photons presents interesting advantages: 1. The reduction of the probability of error with respect to Lloyd's quantum illumination, 2. The reduction of the integration time with respect to Lloyd's quantum illumination, 3. The increase in the ultimate in the measurement of the range-delay accuracy.