A5106746003- Quantum Computing Algorithms and Architecture
- Machine Learning and Algorithms
- Quantum Information and Cryptography
- Complexity and Algorithms in Graphs
- Computability, Logic, AI Algorithms
- Stochastic Gradient Optimization Techniques
- Quantum Mechanics and Applications
- Markov Chains and Monte Carlo Methods
- Cryptography and Data Security
- Quantum-Dot Cellular Automata
- Limits and Structures in Graph Theory
- Mathematical Approximation and Integration
- Optimization and Search Problems
- Random Matrices and Applications
- Point processes and geometric inequalities
- Polynomial and algebraic computation
- Stochastic processes and statistical mechanics
- Advanced Thermodynamics and Statistical Mechanics
- Parallel Computing and Optimization Techniques
- Quantum many-body systems
- Constraint Satisfaction and Optimization
- Matrix Theory and Algorithms
- Machine Learning in Materials Science
- Advanced Mathematical Theories
- Optical Polarization and Ellipsometry
IBM (United States)
2020-2024
Alliance for Safe Kids
2024
IBM Research - Thomas J. Watson Research Center
2021-2023
IBM Research - Almaden
2023
Massachusetts Institute of Technology
2019-2020
QuSoft
2017-2019
Centrum Wiskunde & Informatica
2014-2019
University of Amsterdam
2017-2019
College of Western Idaho
2015-2017
University of Waterloo
2015
Quantum computers offer an intriguing path for a paradigmatic change of computing in the natural sciences and beyond, with potential achieving so-called quantum advantage—namely, significant (in some cases exponential) speedup numerical simulations. The rapid development hardware devices various realizations qubits enables execution small-scale but representative applications on computers. In particular, high-energy physics community plays pivotal role accessing power computing, since field...
This paper surveys quantum learning theory: the theoretical aspects of machine using computers. We describe main results known for three models learning: exact from membership queries, and Probably Approximately Correct (PAC) agnostic classical or examples.
We study the robustness of bucket brigade quantum random access memory model introduced by Giovannetti et al (2008 Phys. Rev. Lett.100 160501). Due to a result Regev and Schiff (ICALP '08 733), we show that for class error models rate per gate in has be order (where is size memory) whenever used as an oracle searching problem. conjecture this case any realistic will encountered practice, algorithms with super-polynomially many queries must small, which further motivates need correction. By...
Quantum computers offer an intriguing path for a paradigmatic change of computing in the natural sciences and beyond, with potential achieving so-called quantum advantage, namely significant (in some cases exponential) speed-up numerical simulations. The rapid development hardware devices various realizations qubits enables execution small scale but representative applications on computers. In particular, high-energy physics community plays pivotal role accessing power computing, since field...
This paper surveys quantum learning theory: the theoretical aspects of machine using computers. We describe main results known for three models learning: exact from membership queries, and Probably Approximately Correct (PAC) agnostic classical or examples.
In learning theory, the VC dimension of a concept class C is most common way to measure its “richness.” A fundamental result says that number examples needed learn an unknown target c∈C under distribution D, tightly determined by d C. Specifically, in PAC model Θ(dϵ+log(1/δ)ϵ) examples are necessary and sufficient for learner output, with probability 1−δ, hypothesis h ϵ-close c (measured D). related agnostic model, where samples need not come from c∈C, we know...
We present classical and quantum algorithms for approximating partition functions of Hamiltonians at a given temperature. Our work has two main contributions: first, we modify the algorithm \v{S}tefankovi\v{c}, Vempala Vigoda (\emph{J.~ACM}, 56(3), 2009) to improve its sample complexity; second, quantize this new algorithm, improving upon previously fastest problem, due Harrow Wei (SODA 2020). The conventional approach estimating requires means Gibbs distributions set inverse temperatures...
The absolute separability problem asks for a characterization of the quantum states $\rho \in M_m\otimes M_n$ with property that $U\rho U^\dagger$ is separable all unitary matrices $U$. We investigate whether or not it case $\rho$ absolutely if and only has positive partial transpose In particular, we develop an easy-to-use method showing entanglement witness map unable to detect in any such state, apply our many well-known criteria, including range criterion, realignment Choi its...
We propose a learning model called the quantum statistical QSQ model, which extends SQ introduced by Kearns to setting. Our can be also seen as restriction of PAC model: here, learner does not have direct access examples, but only obtain estimates measurement statistics on them. Theoretically, this provides simple yet expressive setting explore power examples in machine learning. From practical perspective, since simpler operations are required, algorithms more feasible for implementation...
$ \newcommand{\eps}{\varepsilon} $In learning theory, the VC dimension of a concept class $C$ is most common way to measure its "richness." In PAC model $$ Θ\Big(\frac{d}{\eps} + \frac{\log(1/δ)}{\eps}\Big) examples are necessary and sufficient for learner output, with probability $1-δ$, hypothesis $h$ that $\eps$-close target $c$. related agnostic model, where samples need not come from $c\in C$, we know Θ\Big(\frac{d}{\eps^2} \frac{\log(1/δ)}{\eps^2}\Big) output an $h\in C$ whose error at...
We prove a characterization of $t$-query quantum algorithms in terms the unit ball space degree-$2t$ polynomials. Based on this, we obtain refined notion approximate polynomial degree that equals query complexity, answering question Aaronson et al. (CCC'16). Our proof is based fundamental result Christensen and Sinclair (J. Funct. Anal., 1987) generalizes well-known Stinespring representation for channels to multilinear forms. Using our characterization, show many polynomials four are far...
We present two new results about exact learning by quantum computers. First, we show how to exactly learn a k-Fourier-sparse n-bit Boolean function from O(k^{1.5}(log k)^2) uniform examples for that function. This improves over the bound of Theta~(kn) uniformly random classical (Haviv and Regev, CCC'15). Our main tool is an improvement Chang's lemma sparse functions. Second, if concept class {C} can be learned using Q membership queries, then it also O ({Q^2}/{log Q} * log|C|) queries....
In learning theory, the VC dimension of a concept class [EQUATION] is most common way to measure its richness. A fundamental result says that number examples needed learn an unknown target c e C under distribution D, tightly determined by d C. Specifically, in PAC model[EQUATION]examples are necessary and sufficient for learner output, with probability 1 - δ, hypothesis h e-close (measured D). related agnostic model, where samples need not come from C, we know that[EQUATION]examples output...
We establish the first general connection between design of quantum algorithms and circuit lower bounds. Specifically, let <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathfrak{C}$</tex> be a class polynomial-size concepts, suppose that can PAC-learned with membership queries under uniform distribution error xmlns:xlink="http://www.w3.org/1999/xlink">$1/2 -\gamma$</tex> by time xmlns:xlink="http://www.w3.org/1999/xlink">$T$</tex> algorithm....
We present two new results about exact learning by quantum computers. First, we show how to exactly learn a $k$-Fourier-sparse $n$-bit Boolean function from $O(k^{1.5}(\log k)^2)$ uniform examples for that function. This improves over the bound of $\widetilde{\Theta}(kn)$ uniformly random \emph{classical} (Haviv and Regev, CCC'15). Additionally, provide possible direction improve our $\widetilde{O}(k^{1.5})$ upper proving an improvement Chang's lemma functions. Second, if concept class...
In its usual form, Grover’s quantum search algorithm uses O( √ N) queries and N log other elementary gates to find a solution in an N-bit database. Grover 2002 showed how reduce the number of for special case where database has unique solution, without significantly increasing queries. We show this further log(r) every constant r, sufficiently large N. This means that, on average, circuits between two barely touch more than qubits which acts. For very that is power 2, we can choose r such...
Given a Boolean function f:{ -1,1} ^{n}→ { -1,1, define the Fourier distribution to be on subsets of [n], where each S ⊆ [n] is sampled with probability f ˆ (S) 2 . The Entropy-influence (FEI) conjecture Friedgut and Kalai [28] seeks relate two fundamental measures associated distribution: does there exist universal constant C > 0 such that H(f ˆ2 ) ≤ ⋅ Inf (f), H (fˆ2) Shannon entropy Inf(f) total influence In this article, we present three new contributions toward FEI conjecture: (1)...
We survey various recent results that rigorously study the complexity of learning quantum states. These include progress on tomography, physical states, alternate models to tomography and classical functions encoded as highlight how these are paving way for a highly successful theory with range exciting open questions. To this end, we distill 25 questions from results.