More Like this

1. Gaussian Cooling and Dikin Walks: The Interior-Point Method for Logconcave Sampling

   Kook, Yunbum; Vempala, Santosh S (July 2024, Conference on Learning Theory 2024)

   The connections between (convex) optimization and (logconcave) sampling have been considerably enriched in the past decade with many conceptual and mathematical analogies. For instance, the Langevin algorithm can be viewed as a sampling analogue of gradient descent and has condition-number-dependent guarantees on its performance. In the early 1990s, Nesterov and Nemirovski developed the Interior-Point Method (IPM) for convex optimization based on self-concordant barriers, providing efficient algorithms for structured convex optimization, often faster than the general method. This raises the following question: can we develop an analogous IPM for structured sampling problems? In 2012, Kannan and Narayanan proposed the Dikin walk for uniformly sampling polytopes, and an improved analysis was given in 2020 by Laddha-Lee-Vempala. The Dikin walk uses a local metric defined by a self-concordant barrier for linear constraints. Here we generalize this approach by developing and adapting IPM machinery together with the Dikin walk for poly-time sampling algorithms. Our IPM-based sampling framework provides an efficient warm start and goes beyond uniform distributions and linear constraints. We illustrate the approach on important special cases, in particular giving the fastest algorithms to sample uniform, exponential, or Gaussian distributions on a truncated PSD cone. The framework is general and can be applied to other sampling algorithms. 

   more » « less
2. 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
3. Secret key distillation over a pure loss quantum wiretap channel under restricted eavesdropping

   https://doi.org/10.1109/ISIT.2019.8849223  

   Pan, Ziwen; Seshadreesan, Kaushik P.; Clark, William; Adcock, Mark R.; Djordjevic, Ivan B.; Shapiro, Jeffrey H.; Guha, Saikat (July 2019, 2019 IEEE International Symposium on Information Theory (ISIT))

   Quantum cryptography provides absolute security against an all-powerful eavesdropper (Eve). However, in practice Eve's resources may be restricted to a limited aperture size so that she cannot collect all paraxial light without alerting the communicating parties (Alice and Bob). In this paper we study a quantum wiretap channel in which the connection from Alice to Eve is lossy, so that some of the transmitted quantum information is inaccessible to both Bob and Eve. For a pureloss channel under such restricted eavesdropping, we show that the key rates achievable with a two-mode squeezed vacuum state, heterodyne detection, and public classical communication assistance-given by the Hashing inequality-can exceed the secret key distillation capacity of the channel against an omnipotent eavesdropper. We report upper bounds on the key rates under the restricted eavesdropping model based on the relative entropy of entanglement, which closely match the achievable rates. For the pure-loss channel under restricted eavesdropping, we compare the secret-key rates of continuous-variable (CV) quantum key distribution (QKD) based on Gaussian-modulated coherent states and heterodyne detection with the discrete variable (DV) decoystate BB84 QKD protocol based on polarization qubits encoded in weak coherent laser pulses. 

   more » « less
4. A New Security Proof for Twin-Field Quantum Key Distribution (QKD)

   https://doi.org/10.3390/app14010187  

   Krawec, Walter O. (January 2024, Applied Sciences)

   Twin-field QKD (TF-QKD) protocols allow for increased key rates over long distances when compared to standard QKD protocols. They are even able to surpass the PLOB bound without the need for quantum repeaters. In this work, we revisit a previous TF-QKD protocol and derive a new, simple, proof of security for it. We also look at several variants of the protocol and investigate their performance, showing some interesting behaviors due to the asymmetric nature of the protocol. 

   more » « less
5. Security of Satellite-Based CV-QKD under Realistic Assumptions

   https://doi.org/10.1109/ICTON51198.2020.9203397  

   Pan, Ziwen; Djordjevic, Ivan B. (July 2020, 2020 22nd International Conference on Transparent Optical Networks (ICTON))

   null (Ed.)

   With the vastly growing need for secure communication, quantum key distribution (QKD) has been developed to provide high security for communications against potential attacks from the fast-developing quantum computers. Among different QKD protocols, continuous variable (CV-) QKD employing Gaussian modulated coherent states has been promising for its complete security proof and its compatibility with current communication systems in implementation with homodyne or heterodyne detection. Since satellite communication has been more and more important in developing global communication networks, there have been concerns about the security in satellite communication and how we should evaluate the security of CV-QKD in such scenarios. To better analyse the secure key rate (SKR) in this case, in this invited paper we investigate the CV-QKD SKR lower bounds under realistic assumptions over a satellite-to-satellite channel. We also investigate the eavesdropper's best strategy to apply in these scenarios. We demonstrate that for these channel conditions with well-chosen carrier centre frequency and receiver aperture size, based on channel parameters, we can optimize SKR correspondingly. The proposed satellite-based QKD system provides high security level for the coming 5G and beyond networks, the Internet of things, self-driving cars, and other fast-developing applications. 

   more » « less