Publications related to Solving the Learning Parity with Noise Problem Using Quantum Algorithms

Related publications (20)

The Cost of Consistency: Submodular Maximization with Constant Recourse

In this work, we study online submodular maximization and how the requirement of maintaining a stable solution impacts the approximation. In particular, we seek bounds on the best-possible approximation ratio that is attainable when the algorithm is allowe ...

ACM2025

On the conjugate symmetry and sparsity of the harmonic decomposition of parametric surfaces with the randomised Kaczmarz method

Katrin Beyer

This limitation is circumvented by using scalable and non–memory–intensive harmonic expansions. In this paper, the projection of parametric surfaces onto disk and spherical harmonics bases is investigated, and three novel computationally efficient algorith ...

2024

Energy-Aware Decentralized Learning with Intermittent Model Training

Anne-Marie Kermarrec, Rafael Pereira Pires, Rishi Sharma, Marinus Abraham de Vos, Akash Balasaheb Dhasade

SKIPTRAIN is a novel Decentralized Learning (DL) algorithm, which minimizes energy consumption in decentralized learning by strategically skipping some training rounds and substituting them with synchronization rounds. These trainingsilent periods, besides ...

IEEE2024

Variational benchmarks for quantum many-body problems

Giuseppe Carleo, Andreas Martin Läuchli Herzig, Jannes Willy E. Nys, Filippo Vicentini, Riccardo Rossi, Dian Wu, Imelda Romero

The continued development of computational approaches to many-body ground-state problems in physics and chemistry calls for a consistent way to assess its overall progress. In this work, we introduce a metric of variational accuracy, the V-score, obtained ...

American Association for the Advancement of Science2024

Solving the Tensor Isomorphism Problem for Special Orbits with Low Rank Points: Cryptanalysis and Repair of an Asiacrypt 2023 Commitment Scheme

Laurane Chloé Angélina Marco

The Tensor Isomorphism Problem (TIP) has been shown equivalent to the matrix code equivalence problem, making it an interesting candidate on which to build post-quantum cryptographic primitives. These hard problems have already been used in protocol develo ...

Springer Cham2024

Optimizing Quantum Compilers: Efficient and Effective Algorithms

Fereshte Mozafari Ghoraba

Quantum computing has made significant progress in recent years, with Google and IBM releasing quantum computers with 72 and 50 qubits, respectively. Google has also achieved quantum supremacy with its 54-qubit device, and IBM has announced the release of ...

EPFL2023

Online Network Source Optimization with Graph-Kernel MAB

Pascal Frossard

We propose Grab-UCB, a graph-kernelmulti-arms bandit algorithm to learn online the optimal source placement in large scale networks, such that the reward obtained from a priori unknown network processes is maximized. The uncertainty calls for online learni ...

Springer International Publishing Ag2023

Retraction-based numerical methods for continuation, interpolation and time integration on manifolds

Axel Elie Joseph Séguin

The goal of this thesis is the development and the analysis of numerical methods for problems where the unknown is a curve on a smooth manifold. In particular, the thesis is structured around the three following problems: homotopy continuation, curve inter ...

EPFL2023

Maximum Independent Set: Self-Training through Dynamic Programming

Volkan Cevher, Grigorios Chrysos, Efstratios Panteleimon Skoulakis

This work presents a graph neural network (GNN) framework for solving the maximum independent set (MIS) problem, inspired by dynamic programming (DP). Specifically, given a graph, we propose a DP-like recursive algorithm based on GNNs that firstly construc ...

2023

Signatures of a sampling quantum advantage in driven quantum many-body systems

Thanasilp Supanut

A crucial milestone in the field of quantum simulation and computation is to demonstrate that a quantum device can perform a computation task that is classically intractable. A key question is to identify setups that can achieve such goal within current te ...

IOP Publishing Ltd2023

Distributed Shadow Dynamic Consensus Optimization Framework for Power Market with Parameterization Bidding Strategy of GENCOs

Liying Yu, Sidi-Rachid Cherkaoui

This paper presents a distributed shadow dynamic consensus (DSDC) framework to address the generation company (GENCO) strategic bidding problem in the independent system operator (ISO) operation. First, each sub-group is defined according to the communicat ...

IEEE2023

Practical Compilation of Quantum Programs

Bruno Schmitt Antunes

It's been a little more than 40 years since researchers first suggested exploiting quantum physics to build more powerful computers. During this time, we have seen the development of many quantum algorithms and significant technological advances to make th ...

EPFL2022

Advances in Quantum Computation and Quantum Technologies: A Design Automation Perspective

Giovanni De Micheli

Universal and fault-tolerant quantum computation is a promising new paradigm that may efficiently conquer difficult computation tasks beyond the reach of classical computation. It motivates the development of various quantum technologies. The rapid progres ...

2022

One-particle Green's functions from the quantum equation of motion algorithm

Nicola Marzari, Francesco Libbi

Many-body Green's functions encode all the properties and excitations of interacting electrons. While these are challenging to be evaluated accurately on a classical computer, recent efforts have been directed toward finding quantum algorithms that may pro ...

AMER PHYSICAL SOC2022

Detailed Placement for Dedicated LUT-Level FPGA Interconnect

Paolo Ienne, Grace Zgheib, Stefan Nikolic

In this work, we develop timing-driven CAD support for FPGA architectures with direct connections between LUTs. We do so by proposing an efficient ILP-based detailed placer, which moves a carefully selected subset of LUTs from their original positions, so ...

ASSOC COMPUTING MACHINERY2022

Efficient deterministic preparation of quantum states using decision diagrams

Giovanni De Micheli, Fereshte Mozafari Ghoraba

Loading classical data into quantum registers is one of the most important primitives of quantum computing. While the complexity of preparing a generic quantum state is exponential in the number of qubits, in many practical tasks the state to prepare has a ...

2022

A disaggregate choice-based approach to find ε-equilibria of oligopolistic markets

Michel Bierlaire, Virginie Janine Camille Lurkin, Stefano Bortolomiol

We present a general framework to find ε-equilibrium solutions of oligopolistic markets in which demand is modeled at the disaggregate level using discrete choice models. Consumer choices are modeled according to random utility theory, and the choice proba ...

2021

Low-Rank Approximation In The Frobenius Norm By Column And Row Subset Selection

Daniel Kressner, Alice Cortinovis

A CUR approximation of a matrix A is a particular type of low-rank approximation A approximate to CUR, where C and R consist of columns and rows of A, respectively. One way to obtain such an approximation is to apply column subset selection to A and A(T). ...

SIAM PUBLICATIONS2020

A Unified Theory of Decentralized SGD with Changing Topology and Local Updates

Martin Jaggi, Sebastian Urban Stich, Anastasiia Koloskova

Decentralized stochastic optimization methods have gained a lot of attention recently, mainly because of their cheap per iteration cost, data locality, and their communication-efficiency. In this paper we introduce a unified convergence analysis that cover ...

JMLR-JOURNAL MACHINE LEARNING RESEARCH2020

Compressive sensing adaptation for polynomial chaos expansions

Panagiotis Tsilifis

Basis adaptation in Homogeneous Chaos spaces rely on a suitable rotation of the underlying Gaussian germ. Several rotations have been proposed in the literature resulting in adaptations with different convergence properties. In this paper we present a new ...

ACADEMIC PRESS INC ELSEVIER SCIENCE2019