Explanipedia

Getting almost all the bits from a quantum random access code Open

Han-Hsuan Lin, Ronald de Wolf · 2025

A quantum random access code (QRAC) is a map $x\mapstoρ_x$ that encodes $n$-bit strings $x$ into $m$-qubit quantum states $ρ_x$, in a way that allows us to recover any one bit of $x$ with success probability $\geq p$. The measurement on $ρ…

Overview of the first Wendelstein 7-X long pulse campaign with fully water-cooled plasma facing components Open

O. Grulke, Christopher G. Albert, J. A. Alcusón, P. Aleynikov, K. Aleynikova , et al. · 2024

After a long device enhancement phase, scientific operation resumed in 2022. The main new device components are the water cooling of all plasma facing components and the new water-cooled high heat flux divertor units. Water cooling allowed…

A Quantum Speed-Up for Approximating the Top Eigenvectors of a Matrix Open

Yanlin Chen, András Gilyén, Ronald de Wolf · 2024

Finding a good approximation of the top eigenvector of a given $d\times d$ matrix $A$ is a basic and important computational problem, with many applications. We give two different quantum algorithms that, given query access to the entries …

Generating EPR-pairs from an -party resource state Open

Sergey Bravyi, Yash Sharma, Márió Szegedy, Ronald de Wolf · 2024

Motivated by quantum network applications over classical channels, we initiate the study of -party resource states from which LOCC protocols can create EPR-pairs between any disjoint pairs of parties. We give constructions of such states …

Tight Bounds for Quantum Phase Estimation and Related Problems Open

Nikhil S. Mande, Ronald de Wolf · 2023

Phase estimation, due to Kitaev [arXiv'95], is one of the most fundamental subroutines in quantum computing, used in Shor’s factoring algorithm, optimization algorithms, quantum chemistry algorithms, and many others. In the basic scenario,…

Tight Bounds for the Randomized and Quantum Communication Complexities of Equality with Small Error Open

Olivier Lalonde, Nikhil S. Mande, Ronald de Wolf · 2023

We investigate the randomized and quantum communication complexities of the well-studied Equality function with small error probability ε, getting the optimal constant factors in the leading terms in various different models. The following…

Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving Open

Simon Apers, Ronald de Wolf · 2022

Graph sparsification underlies a large number of algorithms, ranging from\napproximation algorithms for cut problems to solvers for linear systems in the\ngraph Laplacian. In its strongest form, "spectral sparsification" reduces the\nnumbe…

Average-Case Verification of the Quantum Fourier Transform Enables Worst-Case Phase Estimation Open

Noah Linden, Ronald de Wolf · 2022

The quantum Fourier transform (QFT) is a key primitive for quantum computing that is typically used as a subroutine within a larger computation, for instance for phase estimation. As such, we may have little control over the state that is …

Generating $k$ EPR-pairs from an $n$-party resource state Open

Sergey Bravyi, Yash Sharma, Márió Szegedy, Ronald de Wolf · 2022

Motivated by quantum network applications over classical channels, we initiate the study of $n$-party resource states from which LOCC protocols can create EPR-pairs between any $k$ disjoint pairs of parties. We give constructions of such s…

Influence in Completely Bounded Block-multilinear Forms and Classical Simulation of Quantum Algorithms Open

Nikhil Bansal, Makrand Sinha, Ronald de Wolf · 2022

The Aaronson-Ambainis conjecture (Theory of Computing '14) says that every low-degree bounded polynomial on the Boolean hypercube has an influential variable. This conjecture, if true, would imply that the acceptance probability of every $…

Symmetry and Quantum Query-To-Communication Simulation Open

Sourav Chakraborty, Arkadev Chattopadhyay, Peter Høyer, Nikhil S. Mande, Manaswi Paraashar , et al. · 2022

Buhrman, Cleve and Wigderson (STOC'98) showed that for every Boolean function f : {-1,1}ⁿ → {-1,1} and G ∈ {AND₂, XOR₂}, the bounded-error quantum communication complexity of the composed function f∘G equals O(𝖰(f) log n), where 𝖰(f) denot…

Exact quantum query complexity of computing Hamming weight modulo powers of two and three Open

Arjan Cornelissen, Nikhil S. Mande, Māris Ozols, Ronald de Wolf · 2021

We study the problem of computing the Hamming weight of an $n$-bit string modulo $m$, for any positive integer $m \leq n$ whose only prime factors are 2 and 3. We show that the exact quantum query complexity of this problem is $\left\lceil…

Two new results about quantum exact learning Open

Srinivasan Arunachalam, Sourav Chakraborty, Troy Lee, Manaswi Paraashar, Ronald de Wolf · 2021

We present two new results about exact learning by quantum computers. First, we show how to exactly learn a -Fourier-sparse -bit Boolean function from uniform quantum examples for that function. This improves over the bound of uniformly …

Quantum Algorithms and Lower Bounds for Linear Regression with Norm Constraints Open

Yanlin Chen, Ronald de Wolf · 2021

Lasso and Ridge are important minimization problems in machine learning and statistics. They are versions of linear regression with squared loss where the vector $θ\in\mathbb{R}^d$ of coefficients is constrained in either $\ell_1$-norm (fo…

Improved Bounds on Fourier Entropy and Min-entropy Open

Srinivasan Arunachalam, Sourav Chakraborty, Michal Koucký, Nitin Saurabh, Ronald de Wolf · 2021

Given a Boolean function f:{ -1,1} ^{n}→ { -1,1, define the Fourier distribution to be the distribution on subsets of [n], where each S ⊆ [n] is sampled with probability f ˆ (S) 2 . The Fourier Entropy-influence (FEI) conjecture of Friedgu…

Lightweight Detection of a Small Number of Large Errors in a Quantum Circuit Open

Noah Linden, Ronald de Wolf · 2021

Suppose we want to implement a unitary , for instance a circuit for some quantum algorithm. Suppose our actual implementation is a unitary , which we can only apply as a black-box. In general it is an exponentially-hard task to decide whet…

Quantum Algorithms for Matrix Scaling and Matrix Balancing Open

Joran van Apeldoorn, Sander Gribling, Yinan Li, Harold Nieuwboer, Michael Walter , et al. · 2021

Matrix scaling and matrix balancing are two basic linear-algebraic problems with a wide variety of applications, such as approximating the permanent, and pre-conditioning linear systems to make them more numerically stable. We study the po…

Tight Bounds for the Randomized and Quantum Communication Complexities of Equality with Small Error. Open

Nikhil S. Mande, Ronald de Wolf · 2021

We investigate the randomized and quantum communication complexities of the well-studied Equality function with small error probability $\epsilon$, getting the optimal constant factors in the leading terms in a number of different models. …

The Role of Symmetry in Quantum Query-to-Communication Simulation Open

Sourav Chakraborty, Arkadev Chattopadhyay, Peter Høyer, Nikhil S. Mande, Manaswi Paraashar , et al. · 2020

Buhrman, Cleve and Wigderson (STOC'98) showed that for every Boolean function\nf : {-1,1}^n to {-1,1} and G in {AND_2, XOR_2}, the bounded-error quantum\ncommunication complexity of the composed function f o G equals O(Q(f) log n),\nwhere …

The Role of Symmetry in Quantum Query-to-Communication Simulation Open

Sourav Chakraborty, Arkadev Chattopadhyay, Peter Høyer, Nikhil S. Mande, Manaswi Paraashar , et al. · 2020

Buhrman, Cleve and Wigderson (STOC'98) showed that for every Boolean function f : {-1,1}^n to {-1,1} and G in {AND_2, XOR_2}, the bounded-error quantum communication complexity of the composed function f o G equals O(Q(f) log n), where Q(f…

Quantum algorithms for matrix scaling and matrix balancing Open

Joran van Apeldoorn, Sander Gribling, Yinan Li, Harold Nieuwboer, Michael Walter , et al. · 2020

Matrix scaling and matrix balancing are two basic linear-algebraic problems with a wide variety of applications, such as approximating the permanent, and pre-conditioning linear systems to make them more numerically stable. We study the po…

Quantum Speedup for Graph Sparsification, Cut Approximation and Laplacian Solving Open

Simon Apers, Ronald de Wolf · 2020

Graph sparsification underlies a large number of algorithms, ranging from approximation algorithms for cut problems to solvers for linear systems in the graph Laplacian. In its strongest form, "spectral sparsification" reduces the number o…

Improved Quantum Boosting Open

Adam Izdebski, Ronald de Wolf · 2020

Boosting is a general method to convert a weak learner (which generates hypotheses that are just slightly better than random) into a strong learner (which generates hypotheses that are much better than random). Recently, Arunachalam and Ma…

Quantum Coupon Collector Open

Srinivasan Arunachalam, Aleksandrs Belovs, Andrew M. Childs, Robin Kothari, Ansis Rosmanis , et al. · 2020

We study how efficiently a $k$-element set $S\subseteq[n]$ can be learned from a uniform superposition $|S\rangle$ of its elements. One can think of $|S\rangle=\sum_{i\in S}|i\rangle/\sqrt{|S|}$ as the quantum version of a uniformly random…

Quantum coupon collector Open

Srinivasan Arunachalam, Aleksandrs Belovs, Andrew M. Childs, Robin Kothari, Ansis Rosmanis , et al. · 2020

Improved Bounds on Fourier Entropy and Min-Entropy Open

Srinivasan Arunachalam, Sourav Chakraborty, Michal Koucký, Nitin Saurabh, Ronald de Wolf · 2020

Given a Boolean function f:{-1,1}ⁿ→ {-1,1}, define the Fourier distribution to be the distribution on subsets of [n], where each S ⊆ [n] is sampled with probability f̂(S)². The Fourier Entropy-Influence (FEI) conjecture of Friedgut and Kala…

Quantum Speedup for Graph Sparsification, Cut Approximation and Laplacian Solving Open

Simon Apers, Ronald de Wolf · 2019

Graph sparsification underlies a large number of algorithms, ranging from approximation algorithms for cut problems to solvers for linear systems in the graph Laplacian. In its strongest form, "spectral sparsification" reduces the number o…

Quantum Computing: Lecture Notes Open

Ronald de Wolf · 2019

This is a set of lecture notes suitable for a Master's course on quantum computation and information from the perspective of theoretical computer science. The first version was written in 2011, with many extensions and improvements in subs…

Quantum Computing: Lecture Notes Open

Ronald de Wolf · 2019

This is a set of lecture notes suitable for a Master's course on quantum computation and information from the perspective of theoretical computer science. The first version was written in 2011, with many extensions and improvements in subs…

Two new results about quantum exact learning Open

Srinivasan Arunachalam, Sourav Chakraborty, Troy J. Lee, Manaswi Paraashar, Ronald de Wolf · 2019

We present two new results about exact learning by quantum computers. First, we show \nhow to exactly learn a k-Fourier-sparse n-bit Boolean function from O(k1.5(log k)2) uniform \nquantum examples for that function. This improves over the…

Ronald de Wolf YOU? Author Swipe