More Like this

1. Single Observation Adaptive Search for Continuous Simulation

   Kiatsupaibul, Seksan; Smith, Robert L; and Zabinsky, Zelda B. (January 2018, Operations research)

   Optimizing the performance of complex systems modeled by stochastic computer simulations is a challenging task, partly because of the lack of structural properties (e.g., convexity). This challenge is magnified by the presence of random error whereby an adaptive algorithm searching for better designs can at times mistakenly accept an inferior design. In contrast to performing multiple simulations at a design point to estimate the performance of the design, we propose a framework for adaptive search algorithms that executes a single simulation for each design point encountered. Here the estimation errors are reduced by averaging the performances from previously evaluated designs drawn from a shrinking ball around the current design point. We show under mild regularity conditions for continuous design spaces that the accumulated errors, although dependent, form a martingale process, and hence, by the strong law of large numbers for martingales, the average errors converge to zero as the algorithm proceeds. This class of algorithms is shown to converge to a global optimum with probability one. By employing a shrinking ball approach with single observations, an adaptive search algorithm can simultaneously improve the estimates of performance while exploring new and potentially better design points. Numerical experiments offer empirical support for this paradigm of single observation simulation optimization. 

   more » « less
2. Adaptive importance sampling for extreme quantile estimation with stochastic black box computer models

   https://doi.org/10.1002/nav.21938  

   Pan, Qiyun; Byon, Eunshin; Ko, Young Myoung; Lam, Henry (August 2020, Naval Research Logistics (NRL))

   Abstract Quantile is an important quantity in reliability analysis, as it is related to the resistance level for defining failure events. This study develops a computationally efficient sampling method for estimating extreme quantiles using stochastic black box computer models. Importance sampling has been widely employed as a powerful variance reduction technique to reduce estimation uncertainty and improve computational efficiency in many reliability studies. However, when applied to quantile estimation, importance sampling faces challenges, because a good choice of the importance sampling density relies on information about the unknown quantile. We propose an adaptive method that refines the importance sampling density parameter toward the unknown target quantile value along the iterations. The proposed adaptive scheme allows us to use the simulation outcomes obtained in previous iterations for steering the simulation process to focus on important input areas. We prove some convergence properties of the proposed method and show that our approach can achieve variance reduction over crude Monte Carlo sampling. We demonstrate its estimation efficiency through numerical examples and wind turbine case study. 

   more » « less
3. Adaptive Phase Estimation with Squeezed Vacuum Approaching the Quantum Limit

   https://doi.org/10.22331/q-2024-09-25-1480  

   Rodríguez-García, M A; Becerra, F E (September 2024, Quantum)

   Phase estimation plays a central role in communications, sensing, and information processing. Quantum correlated states, such as squeezed states, enable phase estimation beyond the shot-noise limit, and in principle approach the ultimate quantum limit in precision, when paired with optimal quantum measurements. However, physical realizations of optimal quantum measurements for optical phase estimation with quantum-correlated states are still unknown. Here we address this problem by introducing an adaptive Gaussian measurement strategy for optical phase estimation with squeezed vacuum states that, by construction, approaches the quantum limit in precision. This strategy builds from a comprehensive set of locally optimal POVMs through rotations and homodyne measurements and uses the Adaptive Quantum State Estimation framework for optimizing the adaptive measurement process, which, under certain regularity conditions, guarantees asymptotic optimality for this quantum parameter estimation problem. As a result, the adaptive phase estimation strategy based on locally-optimal homodyne measurements achieves the quantum limit within the phase interval of $[0,\pi /2)$. Furthermore, we generalize this strategy by including heterodyne measurements, enabling phase estimation across the full range of phases from $[0,\pi )$, where squeezed vacuum allows for unambiguous phase encoding. Remarkably, for this phase interval, which is the maximum range of phases that can be encoded in squeezed vacuum, this estimation strategy maintains an asymptotic quantum-optimal performance, representing a significant advancement in quantum metrology. 

   more » « less
4. QuantumNAS: Noise-Adaptive Search for Robust Quantum Circuits

   https://doi.org/10.1109/HPCA53966.2022.00057  

   Wang, Hanrui; Ding, Yongshan; Gu, Jiaqi; Lin, Yujun; Pan, David Z.; Chong, Frederic T.; Han, Song (April 2022, 2022 IEEE International Symposium on High-Performance Computer Architecture (HPCA))

   Quantum noise is the key challenge in Noisy Intermediate-Scale Quantum (NISQ) computers. Previous work for mitigating noise has primarily focused on gate-level or pulse-level noise-adaptive compilation. However, limited research has explored a higher level of optimization by making the quantum circuits themselves resilient to noise.In this paper, we propose QuantumNAS, a comprehensive framework for noise-adaptive co-search of the variational circuit and qubit mapping. Variational quantum circuits are a promising approach for constructing quantum neural networks for machine learning and variational ansatzes for quantum simulation. However, finding the best variational circuit and its optimal parameters is challenging due to the large design space and parameter training cost. We propose to decouple the circuit search from parameter training by introducing a novel SuperCircuit. The SuperCircuit is constructed with multiple layers of pre-defined parameterized gates (e.g., U3 and CU3) and trained by iteratively sampling and updating the parameter subsets (SubCircuits) of it. It provides an accurate estimation of SubCircuits performance trained from scratch. Then we perform an evolutionary co-search of SubCircuit and its qubit mapping. The SubCircuit performance is estimated with parameters inherited from SuperCircuit and simulated with real device noise models. Finally, we perform iterative gate pruning and finetuning to remove redundant gates in a fine-grained manner.Extensively evaluated with 12 quantum machine learning (QML) and variational quantum eigensolver (VQE) benchmarks on 14 quantum computers, QuantumNAS significantly outperforms noise-unaware search, human, random, and existing noise-adaptive qubit mapping baselines. For QML tasks, QuantumNAS is the first to demonstrate over 95% 2-class, 85% 4-class, and 32% 10-class classification accuracy on real quantum computers. It also achieves the lowest eigenvalue for VQE tasks on H 2 , H 2 O, LiH, CH 4 , BeH 2 compared with UCCSD baselines. We also open-source the TorchQuantum library for fast training of parameterized quantum circuits to facilitate future research. 

   more » « less
5. Adaptive Newton Sketch: Linear-time Optimization with Quadratic Convergence and Effective Hessian Dimensionality

   Lacotte, Jonathan; Wang, Yifei; Pilanci, Mert (January 2021, Preceedings of the 38th International Conference on Machine Learning)

   We propose a randomized algorithm with quadratic convergence rate for convex optimization problems with a self-concordant, composite, strongly convex objective function. Our method is based on performing an approximate Newton step using a random projection of the Hessian. Our first contribution is to show that, at each iteration, the embedding dimension (or sketch size) can be as small as the effective dimension of the Hessian matrix. Leveraging this novel fundamental result, we design an algorithm with a sketch size proportional to the effective dimension and which exhibits a quadratic rate of convergence. This result dramatically improves on the classical linear-quadratic convergence rates of state-of-theart sub-sampled Newton methods. However, in most practical cases, the effective dimension is not known beforehand, and this raises the question of how to pick a sketch size as small as the effective dimension while preserving a quadratic convergence rate. Our second and main contribution is thus to propose an adaptive sketch size algorithm with quadratic convergence rate and which does not require prior knowledge or estimation of the effective dimension: at each iteration, it starts with a small sketch size, and increases it until quadratic progress is achieved. Importantly, we show that the embedding dimension remains proportional to the effective dimension throughout the entire path and that our method achieves state-of-the-art computational complexity for solving convex optimization programs with a strongly convex component. We discuss and illustrate applications to linear and quadratic programming, as well as logistic regression and other generalized linear models. 

   more » « less