The Programme Committee of TQC 2024 selected 92 out of 460 submissions for a contributed talk (20% acceptance rate).
You may find the contributed talks here.
The list of accepted posters will be published on the 2nd of May, after the poster notification date. The conference schedule will be published in July.
Note on the list: The talks are listed in alphabetical order of title. Later they will be listed by day of presentation. The topic tags were self-selected by the authors upon submission, given the options provided by the PC chairs.
1.
Matthias C. Caro, Marcel Hinsche, Marios Ioannou, Alexander Nietner, Ryan Sweke
Classical Verification of Quantum Learning Talk
2024.
Abstract | Tags: Intersection of quantum information and machine learning
@Talk{T24_26,
title = {Classical Verification of Quantum Learning},
author = {Matthias C. Caro and Marcel Hinsche and Marios Ioannou and Alexander Nietner and Ryan Sweke},
year = {2024},
date = {2024-01-01},
abstract = {Quantum data access and quantum processing can make certain classically intractable learning tasks feasible. However, quantum capabilities will only be available to a select few in the near future. Thus, reliable schemes that allow classical clients to delegate learning to untrusted quantum servers are required to facilitate widespread access to quantum learning advantages. Building on a recently introduced framework of interactive proof systems for classical machine learning by Goldwasser et al. (ITCS 2021), we develop a framework for classical verification of quantum learning. We exhibit learning problems that a classical learner cannot efficiently solve on their own, but that they can efficiently and reliably solve when interacting with an untrusted quantum prover. Concretely, we consider the problems of agnostic learning parities and Fourier-sparse functions with respect to distributions with uniform input marginal. We propose a new quantum data access model that we call "mixture-of-superpositions" quantum examples, based on which we give efficient quantum learning algorithms for these tasks. Moreover, we prove that agnostic quantum parity and Fourier-sparse learning can be efficiently verified by a classical verifier with only random example or statistical query access. Finally, we showcase two general scenarios in learning and verification in which quantum mixture-of-superpositions examples do not lead to sample complexity improvements over classical data. Our results demonstrate that the potential power of quantum data for learning tasks, while not unlimited, can be utilized by classical agents through interaction with untrusted quantum entities.},
keywords = {Intersection of quantum information and machine learning},
pubstate = {published},
tppubtype = {Talk}
}
Quantum data access and quantum processing can make certain classically intractable learning tasks feasible. However, quantum capabilities will only be available to a select few in the near future. Thus, reliable schemes that allow classical clients to delegate learning to untrusted quantum servers are required to facilitate widespread access to quantum learning advantages. Building on a recently introduced framework of interactive proof systems for classical machine learning by Goldwasser et al. (ITCS 2021), we develop a framework for classical verification of quantum learning. We exhibit learning problems that a classical learner cannot efficiently solve on their own, but that they can efficiently and reliably solve when interacting with an untrusted quantum prover. Concretely, we consider the problems of agnostic learning parities and Fourier-sparse functions with respect to distributions with uniform input marginal. We propose a new quantum data access model that we call "mixture-of-superpositions" quantum examples, based on which we give efficient quantum learning algorithms for these tasks. Moreover, we prove that agnostic quantum parity and Fourier-sparse learning can be efficiently verified by a classical verifier with only random example or statistical query access. Finally, we showcase two general scenarios in learning and verification in which quantum mixture-of-superpositions examples do not lead to sample complexity improvements over classical data. Our results demonstrate that the potential power of quantum data for learning tasks, while not unlimited, can be utilized by classical agents through interaction with untrusted quantum entities.
2.
Jonathan Allcock, Jinge Bao, João F. Doriguello, Alessandro Luongo, Miklos Santha
Constant-depth circuits for Uniformly Controlled Gates and Boolean functions with application to quantum memory circuits Talk
2024.
Abstract | Tags: Intersection of quantum information and machine learning, Models of quantum computation
@Talk{T24_8,
title = {Constant-depth circuits for Uniformly Controlled Gates and Boolean functions with application to quantum memory circuits},
author = {Jonathan Allcock and Jinge Bao and João F. Doriguello and Alessandro Luongo and Miklos Santha},
year = {2024},
date = {2024-01-01},
abstract = {We explore the power of the unbounded Fan-Out gate and the Global Tunable gates generated by Ising-type Hamiltonians in constructing constant-depth quantum circuits, with particular attention to quantum memory devices. We propose two types of constant-depth constructions for implementing Uniformly Controlled Gates. These gates include the Fan-In gates defined by $|xrangle|branglemapsto |xrangle|bøplus f(x)rangle$ for $xın0,1^n$ and $bın0,1$, where $f$ is a Boolean function. The first of our constructions is based on computing the one-hot encoding of the control register $|xrangle$, while the second is based on Boolean analysis and exploits different representations of $f$ such as its Fourier expansion. Via these constructions, we obtain constant-depth circuits for the quantum counterparts of read-only and read-write memory devices — Quantum Random Access Memory ($QRAM$) and Quantum Random Access Gate ($QRAG$) — of memory size $n$. The implementation based on one-hot encoding requires either $O(nłognłogłogn)$ ancillae and $O(nłogn)$ Fan-Out gates or $O(nłogn)$ ancillae and $6$ Global Tunable gates. On the other hand, the implementation based on Boolean analysis requires only $2$ Global Tunable gates at the expense of $O(n^2)$ ancillae.},
keywords = {Intersection of quantum information and machine learning, Models of quantum computation},
pubstate = {published},
tppubtype = {Talk}
}
We explore the power of the unbounded Fan-Out gate and the Global Tunable gates generated by Ising-type Hamiltonians in constructing constant-depth quantum circuits, with particular attention to quantum memory devices. We propose two types of constant-depth constructions for implementing Uniformly Controlled Gates. These gates include the Fan-In gates defined by $|xrangle|branglemapsto |xrangle|bøplus f(x)rangle$ for $xın0,1^n$ and $bın0,1$, where $f$ is a Boolean function. The first of our constructions is based on computing the one-hot encoding of the control register $|xrangle$, while the second is based on Boolean analysis and exploits different representations of $f$ such as its Fourier expansion. Via these constructions, we obtain constant-depth circuits for the quantum counterparts of read-only and read-write memory devices — Quantum Random Access Memory ($QRAM$) and Quantum Random Access Gate ($QRAG$) — of memory size $n$. The implementation based on one-hot encoding requires either $O(nłognłogłogn)$ ancillae and $O(nłogn)$ Fan-Out gates or $O(nłogn)$ ancillae and $6$ Global Tunable gates. On the other hand, the implementation based on Boolean analysis requires only $2$ Global Tunable gates at the expense of $O(n^2)$ ancillae.
3.
Robbie King, Kianna Wan, Jarrod McClean
Exponential learning advantages with conjugate states and minimal quantum memory Talk
2024.
Abstract | Tags: Intersection of quantum information and machine learning, Quantum algorithms, Quantum estimation and measurement
@Talk{T24_274,
title = {Exponential learning advantages with conjugate states and minimal quantum memory},
author = {Robbie King and Kianna Wan and Jarrod McClean},
year = {2024},
date = {2024-01-01},
abstract = {The ability of quantum computers to directly manipulate and analyze quantum states stored in quantum memory allows them to learn about aspects of our physical world that would otherwise be invisible given a modest number of measurements. Here we investigate a new learning resource which could be available to quantum computers in the future – measurements on the unknown state accompanied by its complex conjugate ρ⊗ρ*. For a certain shadow tomography task, we surprisingly find that measurements on only copies of ρ⊗ρ* can be exponentially more powerful than measurements on ρ⊗K, even for large K. This expands the class of exponential advantages using only a constant overhead quantum memory, or minimal quantum memory, and we provide a number of examples where the state ρ* is naturally available in both computational and physical applications. In addition, we precisely quantify the power of classical shadows on single copies under a generalized Clifford ensemble and give a class of quantities that can be efficiently learned. The learning task we study in both the single copy and quantum memory is physically natural and corresponds to real-space observables with a limit of bosonic modes, where it achieves an exponential improvement in detecting certain signals under a noisy background. In addition to quantifying a fundamentally new and powerful resource in quantum learning, we believe the advantage may find applications in improving quantum simulation, learning from quantum sensors, and uncovering new physical phenomena.},
keywords = {Intersection of quantum information and machine learning, Quantum algorithms, Quantum estimation and measurement},
pubstate = {published},
tppubtype = {Talk}
}
The ability of quantum computers to directly manipulate and analyze quantum states stored in quantum memory allows them to learn about aspects of our physical world that would otherwise be invisible given a modest number of measurements. Here we investigate a new learning resource which could be available to quantum computers in the future – measurements on the unknown state accompanied by its complex conjugate ρ⊗ρ*. For a certain shadow tomography task, we surprisingly find that measurements on only copies of ρ⊗ρ* can be exponentially more powerful than measurements on ρ⊗K, even for large K. This expands the class of exponential advantages using only a constant overhead quantum memory, or minimal quantum memory, and we provide a number of examples where the state ρ* is naturally available in both computational and physical applications. In addition, we precisely quantify the power of classical shadows on single copies under a generalized Clifford ensemble and give a class of quantities that can be efficiently learned. The learning task we study in both the single copy and quantum memory is physically natural and corresponds to real-space observables with a limit of bosonic modes, where it achieves an exponential improvement in detecting certain signals under a noisy background. In addition to quantifying a fundamentally new and powerful resource in quantum learning, we believe the advantage may find applications in improving quantum simulation, learning from quantum sensors, and uncovering new physical phenomena.
4.
Andreas Bluhm, Matthias C. Caro, Aadil Oufkir
Hamiltonian Property Testing Talk
2024.
Abstract | Tags: Intersection of quantum information and machine learning, Quantum estimation and measurement
@Talk{T24_182,
title = {Hamiltonian Property Testing},
author = {Andreas Bluhm and Matthias C. Caro and Aadil Oufkir},
year = {2024},
date = {2024-01-01},
abstract = {Locality is a fundamental feature of many physical time evolutions. Assumptions on locality and related structural properties also underlie recently proposed procedures for learning an unknown Hamiltonian from access to the induced time evolution. However, no protocols to rigorously test whether an unknown Hamiltonian is in fact local were known. We investigate Hamiltonian locality testing as a property testing problem, where the task is to determine whether an unknown Hamiltonian $H$ is $k$-local or ε-far from all $k$-local Hamiltonians, given access to the time evolution along $H$. First, we emphasize the importance of the chosen distance measure: With respect to the operator norm, a worst-case distance measure, incoherent quantum locality testers require $TildeØmega(2^n)$ many time evolution queries and an expected total evolution time of $TildeØmega(2^n/ε)$, and even coherent testers need $Ømega(2^n/2)$ many queries and $Ømega(2^n/2/ε)$ total evolution time. In contrast, when distances are measured according to the normalized Frobenius norm, corresponding to an average-case distance, we give a sample-, time-, and computationally efficient incoherent Hamiltonian locality testing algorithm based on randomized measurements. In fact, our procedure can be used to simultaneously test a wide class of Hamiltonian properties beyond locality. Finally, we prove that learning a general Hamiltonian remains exponentially hard with this average-case distance, thereby establishing an exponential separation between Hamiltonian testing and learning. Our work initiates the study of property testing for quantum Hamiltonians, demonstrating that a broad class of Hamiltonian properties is efficiently testable even with limited quantum capabilities, and positioning Hamiltonian testing as an independent area of research alongside Hamiltonian learning.},
keywords = {Intersection of quantum information and machine learning, Quantum estimation and measurement},
pubstate = {published},
tppubtype = {Talk}
}
Locality is a fundamental feature of many physical time evolutions. Assumptions on locality and related structural properties also underlie recently proposed procedures for learning an unknown Hamiltonian from access to the induced time evolution. However, no protocols to rigorously test whether an unknown Hamiltonian is in fact local were known. We investigate Hamiltonian locality testing as a property testing problem, where the task is to determine whether an unknown Hamiltonian $H$ is $k$-local or ε-far from all $k$-local Hamiltonians, given access to the time evolution along $H$. First, we emphasize the importance of the chosen distance measure: With respect to the operator norm, a worst-case distance measure, incoherent quantum locality testers require $TildeØmega(2^n)$ many time evolution queries and an expected total evolution time of $TildeØmega(2^n/ε)$, and even coherent testers need $Ømega(2^n/2)$ many queries and $Ømega(2^n/2/ε)$ total evolution time. In contrast, when distances are measured according to the normalized Frobenius norm, corresponding to an average-case distance, we give a sample-, time-, and computationally efficient incoherent Hamiltonian locality testing algorithm based on randomized measurements. In fact, our procedure can be used to simultaneously test a wide class of Hamiltonian properties beyond locality. Finally, we prove that learning a general Hamiltonian remains exponentially hard with this average-case distance, thereby establishing an exponential separation between Hamiltonian testing and learning. Our work initiates the study of property testing for quantum Hamiltonians, demonstrating that a broad class of Hamiltonian properties is efficiently testable even with limited quantum capabilities, and positioning Hamiltonian testing as an independent area of research alongside Hamiltonian learning.
5.
Matthias C. Caro, Tom Gur, Cambyse Rouze, Daniel Stilck França, Sathyawageeswar Subramanian
Information-theoretic generalization bounds for learning from quantum data Talk
2024.
Abstract | Tags: Intersection of quantum information and machine learning, Quantum information theory
@Talk{T24_185,
title = {Information-theoretic generalization bounds for learning from quantum data},
author = {Matthias C. Caro and Tom Gur and Cambyse Rouze and Daniel Stilck França and Sathyawageeswar Subramanian},
year = {2024},
date = {2024-01-01},
abstract = {Learning tasks play an increasingly prominent role in quantum information and computation. They range from fundamental problems such as state discrimination and metrology over the framework of quantum probably approximately correct (PAC) learning, to the recently proposed shadow variants of state tomography. However, the many directions of quantum learning theory have so far evolved separately. We propose a general mathematical formalism for describing quantum learning by training on classical-quantum data and then testing how well the learned hypothesis generalizes to new data. In this framework, we prove bounds on the expected generalization error of a quantum learner in terms of classical and quantum mutual information quantities measuring how strongly the learner's hypothesis depends on the specific data seen during training. To achieve this, we use tools from quantum optimal transport and quantum concentration inequalities to establish non-commutative versions of decoupling lemmas that underlie recent information-theoretic generalization bounds for classical machine learning. Our framework encompasses and gives intuitively accessible generalization bounds for a variety of quantum learning scenarios such as quantum state discrimination, PAC learning quantum states, quantum parameter estimation, and quantumly PAC learning classical functions. Thereby, our work lays a foundation for a unifying quantum information-theoretic perspective on quantum learning.},
keywords = {Intersection of quantum information and machine learning, Quantum information theory},
pubstate = {published},
tppubtype = {Talk}
}
Learning tasks play an increasingly prominent role in quantum information and computation. They range from fundamental problems such as state discrimination and metrology over the framework of quantum probably approximately correct (PAC) learning, to the recently proposed shadow variants of state tomography. However, the many directions of quantum learning theory have so far evolved separately. We propose a general mathematical formalism for describing quantum learning by training on classical-quantum data and then testing how well the learned hypothesis generalizes to new data. In this framework, we prove bounds on the expected generalization error of a quantum learner in terms of classical and quantum mutual information quantities measuring how strongly the learner's hypothesis depends on the specific data seen during training. To achieve this, we use tools from quantum optimal transport and quantum concentration inequalities to establish non-commutative versions of decoupling lemmas that underlie recent information-theoretic generalization bounds for classical machine learning. Our framework encompasses and gives intuitively accessible generalization bounds for a variety of quantum learning scenarios such as quantum state discrimination, PAC learning quantum states, quantum parameter estimation, and quantumly PAC learning classical functions. Thereby, our work lays a foundation for a unifying quantum information-theoretic perspective on quantum learning.
6.
Srinivasan Arunachalam, Arkopal Dutt, Francisco Escudero Gutiérrez, Carlos Palazuelos
Learning low-degree quantum objects Talk
2024.
Abstract | Tags: Intersection of quantum information and machine learning, Quantum algorithms, Quantum complexity theory
@Talk{T24_290,
title = {Learning low-degree quantum objects},
author = {Srinivasan Arunachalam and Arkopal Dutt and Francisco Escudero Gutiérrez and Carlos Palazuelos},
year = {2024},
date = {2024-01-01},
abstract = {We consider the problem of learning low-degree quantum objects up to ε-error in l_2-distance. We show the following results: (I) unknown n-qubit degree-d (in the Pauli basis) quantum channels and unitaries can be learned using O(1/ε^d) queries (which is independent of n), (II) polynomials p:-1,1^n -> [-1,1] arising from d-query quantum algorithms can be learned from O((1/ε)^d log n) many random examples (x,p(x)) (which implies learnability even for d=O(log n)), and (III) degree-d polynomials p:-1,1^n -> [-1,1] can be learned through O(1/ε^d) queries to a quantum unitary Up that block-encodes p. Our main technical contributions are new Bohnenblust-Hille inequalities for quantum channels and completely bounded polynomials.},
keywords = {Intersection of quantum information and machine learning, Quantum algorithms, Quantum complexity theory},
pubstate = {published},
tppubtype = {Talk}
}
We consider the problem of learning low-degree quantum objects up to ε-error in l_2-distance. We show the following results: (I) unknown n-qubit degree-d (in the Pauli basis) quantum channels and unitaries can be learned using O(1/ε^d) queries (which is independent of n), (II) polynomials p:-1,1^n -> [-1,1] arising from d-query quantum algorithms can be learned from O((1/ε)^d log n) many random examples (x,p(x)) (which implies learnability even for d=O(log n)), and (III) degree-d polynomials p:-1,1^n -> [-1,1] can be learned through O(1/ε^d) queries to a quantum unitary Up that block-encodes p. Our main technical contributions are new Bohnenblust-Hille inequalities for quantum channels and completely bounded polynomials.
7.
Antonio Anna Mele, Armando Angrisani, Soumik Ghosh, Sumeet Khatri, Jens Eisert, Daniel Stilck Franca, Yihui Quek
Noise-induced shallow circuits and absence of barren plateaus Talk
2024.
Abstract | Tags: Intersection of quantum information and machine learning, Other, Quantum complexity theory, Simulation of quantum systems
@Talk{T24_409,
title = {Noise-induced shallow circuits and absence of barren plateaus},
author = {Antonio Anna Mele and Armando Angrisani and Soumik Ghosh and Sumeet Khatri and Jens Eisert and Daniel Stilck Franca and Yihui Quek},
year = {2024},
date = {2024-01-01},
abstract = {We study the impact of non-unital noise on random quantum circuits, generalizing many previous results about the impact of noise on near-term computation that assumed that noise was unital or even specifically depolarizing. Non-unital noise (a class that includes amplitude damping noise and other loss processes) is a more natural noise model for certain physical platforms than unital noise. Yet it is analytically more challenging and has in the past led to starkly different conclusions about computational tasks, like error correction and random circuit sampling. Our main result is that non-unital noise ``truncates" deep random quantum circuits to effectively have logarithmic depth, in the task of computing Pauli expectation values. By way of proving this, we contribute a contraction result for quantum circuits under non-unital noise, which significantly strengthens all previous results in this setting. As an application, we show that circuits used for variational quantum algorithms, under non-unital noise, avoid the problem of barren plateaus for cost functions made of local observables. This is not necessarily good news, however, as their effective shallowness also makes such circuits vulnerable to classical simulators. Accordingly, we also provide an algorithm to estimate local expectation values in the presence of non-unital noise, that succeeds with high probability over the ensemble. The runtime of our algorithm is independent of both the number of qubits and circuit depth, and depends polynomially on the accuracy for one-dimensional architectures and quasi-polynomially for two-dimensional ones. While the hardness of sampling from random circuits under non–unital noise is yet unresolved, our results indicate that for the vast majority of quantum circuits under non-unital noise, we are unlikely to glean quantum advantage for algorithms that output expectation values.},
keywords = {Intersection of quantum information and machine learning, Other, Quantum complexity theory, Simulation of quantum systems},
pubstate = {published},
tppubtype = {Talk}
}
We study the impact of non-unital noise on random quantum circuits, generalizing many previous results about the impact of noise on near-term computation that assumed that noise was unital or even specifically depolarizing. Non-unital noise (a class that includes amplitude damping noise and other loss processes) is a more natural noise model for certain physical platforms than unital noise. Yet it is analytically more challenging and has in the past led to starkly different conclusions about computational tasks, like error correction and random circuit sampling. Our main result is that non-unital noise ``truncates" deep random quantum circuits to effectively have logarithmic depth, in the task of computing Pauli expectation values. By way of proving this, we contribute a contraction result for quantum circuits under non-unital noise, which significantly strengthens all previous results in this setting. As an application, we show that circuits used for variational quantum algorithms, under non-unital noise, avoid the problem of barren plateaus for cost functions made of local observables. This is not necessarily good news, however, as their effective shallowness also makes such circuits vulnerable to classical simulators. Accordingly, we also provide an algorithm to estimate local expectation values in the presence of non-unital noise, that succeeds with high probability over the ensemble. The runtime of our algorithm is independent of both the number of qubits and circuit depth, and depends polynomially on the accuracy for one-dimensional architectures and quasi-polynomially for two-dimensional ones. While the hardness of sampling from random circuits under non–unital noise is yet unresolved, our results indicate that for the vast majority of quantum circuits under non-unital noise, we are unlikely to glean quantum advantage for algorithms that output expectation values.
8.
Srinivasan Arunachalam, Vojtech Havlicek, Louis Schatzki
On the Role of Entanglement and Statistics in Learning Talk
2024.
Abstract | Tags: Intersection of quantum information and machine learning, Models of quantum computation, Quantum algorithms, Quantum complexity theory, Quantum error correction and fault-tolerant quantum computing
@Talk{T24_251,
title = {On the Role of Entanglement and Statistics in Learning},
author = {Srinivasan Arunachalam and Vojtech Havlicek and Louis Schatzki},
year = {2024},
date = {2024-01-01},
abstract = {We make progress in understanding the relationship between learning models with access to entangled, separable and statistical measurements in the quantum statistical query (QSQ) model. We show the following results. Entangled versus separable measurements: The goal is to learn an unknown f from the concept class C containing functions from 0,1^n to [k] given copies of a uniform superposition over |x,f(x)>. We show that, if T copies suffice to learn f using entangled measurements, O(nT^2) copies suffice to learn f using only separable measurements. Entangled versus statistical measurements: The goal is to learn a function f in C given access to separable measurements or statistical measurements. We exhibit a concept class C based of degree-2 functions with exponential separation between QSQ learning and quantum learning with entangled measurements (even in the presence of noise). This proves the "quantum analogue" of the seminal result of Blum et al. that separates classical SQ learning from classical PAC learning with classification noise. QSQ lower bounds for learning states: We introduce a quantum statistical query dimension (QSD), and use it to give lower bounds on the QSQ complexity of learning. We prove superpolynomial QSQ lower bounds for testing purity of quantum states, shadow tomography, learning coset states for the Abelian hidden subgroup problem, degree-2 functions, planted biclique states, and learning output states of Clifford circuits of depth polylog(n). We also show that an extension of QSD characterizes the complexity of general search problems. Further applications: We give an unconditional separation between weak and strong error mitigation and prove lower bounds for learning distributions in the QSQ model. Prior works by Quek et al., Hinsche et al., and Nietner et al. proved analogous results assuming diagonal measurements and our work removes this assumption.},
keywords = {Intersection of quantum information and machine learning, Models of quantum computation, Quantum algorithms, Quantum complexity theory, Quantum error correction and fault-tolerant quantum computing},
pubstate = {published},
tppubtype = {Talk}
}
We make progress in understanding the relationship between learning models with access to entangled, separable and statistical measurements in the quantum statistical query (QSQ) model. We show the following results. Entangled versus separable measurements: The goal is to learn an unknown f from the concept class C containing functions from 0,1^n to [k] given copies of a uniform superposition over |x,f(x)>. We show that, if T copies suffice to learn f using entangled measurements, O(nT^2) copies suffice to learn f using only separable measurements. Entangled versus statistical measurements: The goal is to learn a function f in C given access to separable measurements or statistical measurements. We exhibit a concept class C based of degree-2 functions with exponential separation between QSQ learning and quantum learning with entangled measurements (even in the presence of noise). This proves the "quantum analogue" of the seminal result of Blum et al. that separates classical SQ learning from classical PAC learning with classification noise. QSQ lower bounds for learning states: We introduce a quantum statistical query dimension (QSD), and use it to give lower bounds on the QSQ complexity of learning. We prove superpolynomial QSQ lower bounds for testing purity of quantum states, shadow tomography, learning coset states for the Abelian hidden subgroup problem, degree-2 functions, planted biclique states, and learning output states of Clifford circuits of depth polylog(n). We also show that an extension of QSD characterizes the complexity of general search problems. Further applications: We give an unconditional separation between weak and strong error mitigation and prove lower bounds for learning distributions in the QSQ model. Prior works by Quek et al., Hinsche et al., and Nietner et al. proved analogous results assuming diagonal measurements and our work removes this assumption.
9.
Ashwin Nayak, Pulkit Sinha
Proper vs Improper Quantum PAC Learning Talk
2024.
Abstract | Tags: Intersection of quantum information and machine learning, Quantum algorithms, Quantum complexity theory
@Talk{T24_257,
title = {Proper vs Improper Quantum PAC Learning},
author = {Ashwin Nayak and Pulkit Sinha},
year = {2024},
date = {2024-01-01},
abstract = {A basic question in the PAC model of learning is whether proper learning is harder than improper learning. In the classical case, the answer to this question, with respect to sample complexity, is known to depend on the concept class. While there are concept classes for which the two modes of learning have the same complexity, there are examples of concept classes with VC dimension d that have sample complexity Ω ( d/ε log 1/ε) for proper learning with error ε, while the complexity for improper learning is O( d/ε). One such example arises from the Coupon Collector problem. Motivated by the efficiency of proper versus improper learning with quantum samples, Arunachalam, Belovs, Childs, Kothari, Rosmanis, and de Wolf [1] studied an analogue, the Quantum Coupon Collector problem. Curiously, they discovered that for learning size k subsets of [n] the problem has sample complexity Θ(k log min k, n − k + 1), in contrast with the complexity of Θ(k log k) for Coupon Collector. This effectively negates the possibility of a separation between the two modes of learning via the quantum problem, and Arunachalam et al. posed the possibility of such a separation as an open question. In this work, we first present an algorithm for the Quantum Coupon Collector problem with sample complexity that matches the sharper lower bound of (1 − o_k(1))k ln min k, n − k + 1 shown recently by Bab Hadiashar, Nayak, and Sinha [7], for the entire range of the parameter k. Next, we devise a variant of the problem, the Quantum Padded Coupon Collector. We prove that its sample complexity matches that of the classical Coupon Collector problem for both modes of learning, thereby exhibiting the same asymptotic separation between proper and improper quantum learning as mentioned above. The techniques we develop in the process can be directly applied to any form of padded quantum data. We hope that padding can more generally lift other forms of classical learning behaviour to the quantum setting.},
keywords = {Intersection of quantum information and machine learning, Quantum algorithms, Quantum complexity theory},
pubstate = {published},
tppubtype = {Talk}
}
A basic question in the PAC model of learning is whether proper learning is harder than improper learning. In the classical case, the answer to this question, with respect to sample complexity, is known to depend on the concept class. While there are concept classes for which the two modes of learning have the same complexity, there are examples of concept classes with VC dimension d that have sample complexity Ω ( d/ε log 1/ε) for proper learning with error ε, while the complexity for improper learning is O( d/ε). One such example arises from the Coupon Collector problem. Motivated by the efficiency of proper versus improper learning with quantum samples, Arunachalam, Belovs, Childs, Kothari, Rosmanis, and de Wolf [1] studied an analogue, the Quantum Coupon Collector problem. Curiously, they discovered that for learning size k subsets of [n] the problem has sample complexity Θ(k log min k, n − k + 1), in contrast with the complexity of Θ(k log k) for Coupon Collector. This effectively negates the possibility of a separation between the two modes of learning via the quantum problem, and Arunachalam et al. posed the possibility of such a separation as an open question. In this work, we first present an algorithm for the Quantum Coupon Collector problem with sample complexity that matches the sharper lower bound of (1 − o_k(1))k ln min k, n − k + 1 shown recently by Bab Hadiashar, Nayak, and Sinha [7], for the entire range of the parameter k. Next, we devise a variant of the problem, the Quantum Padded Coupon Collector. We prove that its sample complexity matches that of the classical Coupon Collector problem for both modes of learning, thereby exhibiting the same asymptotic separation between proper and improper quantum learning as mentioned above. The techniques we develop in the process can be directly applied to any form of padded quantum data. We hope that padding can more generally lift other forms of classical learning behaviour to the quantum setting.
10.
Alexander Volberg, Haonan Zhang, Ohad Klein, Joseph Slote
Quantum Bohnenblust–Hille inequalities and applications to learning low-degree quantum observables Talk
2024.
Abstract | Tags: Intersection of quantum information and machine learning, Quantum algorithms, Quantum estimation and measurement
@Talk{T24_425,
title = {Quantum Bohnenblust–Hille inequalities and applications to learning low-degree quantum observables},
author = {Alexander Volberg and Haonan Zhang and Ohad Klein and Joseph Slote},
year = {2024},
date = {2024-01-01},
abstract = {Analysis on the Boolean hypercube −1,1^n, particularly Fourier analysis, has played a crucial role in many areas of mathematics and computer science, including learning algorithms. In view of the success and importance of quantum algorithms, it is natural to transfer classical learning results to the quantum realm. In this contribution, we extend the recent progress on learning low-degree functions and quantum operators to the setting of general qudit systems, as well as develop novel Fourier-analytic tools for studying (generalized) Pauli decompositions of Hermitian operators. These tools also allow us to deduce new results in quantum Boolean analysis and approximate theory, such as the junta-type theorem and dimension-free discrete Remez-type inequalities.},
keywords = {Intersection of quantum information and machine learning, Quantum algorithms, Quantum estimation and measurement},
pubstate = {published},
tppubtype = {Talk}
}
Analysis on the Boolean hypercube −1,1^n, particularly Fourier analysis, has played a crucial role in many areas of mathematics and computer science, including learning algorithms. In view of the success and importance of quantum algorithms, it is natural to transfer classical learning results to the quantum realm. In this contribution, we extend the recent progress on learning low-degree functions and quantum operators to the setting of general qudit systems, as well as develop novel Fourier-analytic tools for studying (generalized) Pauli decompositions of Hermitian operators. These tools also allow us to deduce new results in quantum Boolean analysis and approximate theory, such as the junta-type theorem and dimension-free discrete Remez-type inequalities.
11.
Nai-Hui Chia, Daniel Liang, Fang Song
Quantum State Learning Implies Circuit Lower Bounds Talk
2024.
Abstract | Tags: Intersection of quantum information and machine learning, Quantum complexity theory
@Talk{T24_348,
title = {Quantum State Learning Implies Circuit Lower Bounds},
author = {Nai-Hui Chia and Daniel Liang and Fang Song},
year = {2024},
date = {2024-01-01},
abstract = {We establish connections between state tomography, pseudorandomness, state synthesis lower bounds, and classical circuit lower bounds. In particular, let C be a class of quantum states that can be prepared by a non-uniform family of poly-size quantum circuits. We show that if there exists an algorithm that, given copies of a quantum state, distinguishes whether it is in C or is Haar random, promised one of these is the case, that uses at most O(2^n^2) time and 2^n^0.99 samples then stateBQE is not a subset of stateC. Here stateBQE = stateBQTIME[2^O(n)] and stateC are state synthesis complexity classes as introduced by (Rosenthal and Yuen 2022), which capture problems with classical inputs but quantum output. We prove formally that efficient tomography implies an efficient distinguishing algorithm, so the ability to do sufficiently fast tomography also implies state synthesis lower bounds for C. Finally, combined with a result from (Rosenthal 2024), our result says that an O(2^n^2)-time and 2^n^0.99-sample algorithm that distinguishes QAC^0_f states from Haar random implies EXP is not a subset of TC^0, which would be a monumental breakthrough in classical circuit complexity. This help sheds light on why time-efficient learning algorithms for non-uniform quantum circuit classes has only had limited and partial progress. Our work parallels results in (Arunachalam, Grilo, Gur, Oliveira, and Sundaram 2022) that revealed a similar connection between quantum learning of Boolean functions and circuit lower bounds for classical circuit classes. For instance, just as they constructed a novel conditional pseudorandom generator secure against uniform sub-exponential-time quantum computations, we likewise construct a conditional pseudorandom state (ensemble) that is secure against uniform sub-exponential-time quantum computation and which relies on the complexity theoretic assumption that PSPACE is not a subset of BQSUBEXP. We also establish circuit size hierarchy theorems for non-uniform state synthesis and connections between state synthesis class separations and decision class separations, which may be of independent interest.},
keywords = {Intersection of quantum information and machine learning, Quantum complexity theory},
pubstate = {published},
tppubtype = {Talk}
}
We establish connections between state tomography, pseudorandomness, state synthesis lower bounds, and classical circuit lower bounds. In particular, let C be a class of quantum states that can be prepared by a non-uniform family of poly-size quantum circuits. We show that if there exists an algorithm that, given copies of a quantum state, distinguishes whether it is in C or is Haar random, promised one of these is the case, that uses at most O(2^n^2) time and 2^n^0.99 samples then stateBQE is not a subset of stateC. Here stateBQE = stateBQTIME[2^O(n)] and stateC are state synthesis complexity classes as introduced by (Rosenthal and Yuen 2022), which capture problems with classical inputs but quantum output. We prove formally that efficient tomography implies an efficient distinguishing algorithm, so the ability to do sufficiently fast tomography also implies state synthesis lower bounds for C. Finally, combined with a result from (Rosenthal 2024), our result says that an O(2^n^2)-time and 2^n^0.99-sample algorithm that distinguishes QAC^0_f states from Haar random implies EXP is not a subset of TC^0, which would be a monumental breakthrough in classical circuit complexity. This help sheds light on why time-efficient learning algorithms for non-uniform quantum circuit classes has only had limited and partial progress. Our work parallels results in (Arunachalam, Grilo, Gur, Oliveira, and Sundaram 2022) that revealed a similar connection between quantum learning of Boolean functions and circuit lower bounds for classical circuit classes. For instance, just as they constructed a novel conditional pseudorandom generator secure against uniform sub-exponential-time quantum computations, we likewise construct a conditional pseudorandom state (ensemble) that is secure against uniform sub-exponential-time quantum computation and which relies on the complexity theoretic assumption that PSPACE is not a subset of BQSUBEXP. We also establish circuit size hierarchy theorems for non-uniform state synthesis and connections between state synthesis class separations and decision class separations, which may be of independent interest.
12.
Nahuel L. Diaz, Diego García-Martín, Sujay Kazi, Martin Larocca, Marco Cerezo
Showcasing a Barren Plateau Theory Beyond the Dynamical Lie Algebra Talk
2024.
Abstract | Tags: Intersection of quantum information and machine learning, Quantum algorithms, Quantum information theory
@Talk{T24_230,
title = {Showcasing a Barren Plateau Theory Beyond the Dynamical Lie Algebra},
author = {Nahuel L. Diaz and Diego García-Martín and Sujay Kazi and Martin Larocca and Marco Cerezo},
year = {2024},
date = {2024-01-01},
abstract = {Barren plateaus have emerged as a pivotal challenge for variational quantum computing. Our understanding of this phenomenon underwent a transformative shift with the recent introduction of a Lie algebraic theory capable of explaining most sources of barren plateaus. However, this theory requires either initial states or observables that lie in the circuit's Lie algebra. Focusing on parametrized matchgate circuits, in this work we are able to go beyond this assumption and provide an exact formula for the loss function variance that is valid for arbitrary input states and measurements. Our results reveal that new phenomena emerge when the Lie algebra constraint is relaxed. For instance, we find that the variance does not necessarily vanish inversely with the Lie algebra's dimension. Instead, this measure of expressivity is replaced by a generalized expressivity quantity: the dimension of the Lie group modules. By characterizing the operators in these modules as products of Majorana operators, we can introduce a precise notion of generalized globality and show that measuring generalized-global operators leads to barren plateaus. Our work also provides operational meaning to the generalized entanglement as we connect it with known fermionic entanglement measures, and show that it satisfies a monogamy relation. Finally, while parameterized matchgate circuits are not efficiently simulable in general, our results suggest that the structure allowing for trainability may also lead to classical simulability.},
keywords = {Intersection of quantum information and machine learning, Quantum algorithms, Quantum information theory},
pubstate = {published},
tppubtype = {Talk}
}
Barren plateaus have emerged as a pivotal challenge for variational quantum computing. Our understanding of this phenomenon underwent a transformative shift with the recent introduction of a Lie algebraic theory capable of explaining most sources of barren plateaus. However, this theory requires either initial states or observables that lie in the circuit's Lie algebra. Focusing on parametrized matchgate circuits, in this work we are able to go beyond this assumption and provide an exact formula for the loss function variance that is valid for arbitrary input states and measurements. Our results reveal that new phenomena emerge when the Lie algebra constraint is relaxed. For instance, we find that the variance does not necessarily vanish inversely with the Lie algebra's dimension. Instead, this measure of expressivity is replaced by a generalized expressivity quantity: the dimension of the Lie group modules. By characterizing the operators in these modules as products of Majorana operators, we can introduce a precise notion of generalized globality and show that measuring generalized-global operators leads to barren plateaus. Our work also provides operational meaning to the generalized entanglement as we connect it with known fermionic entanglement measures, and show that it satisfies a monogamy relation. Finally, while parameterized matchgate circuits are not efficiently simulable in general, our results suggest that the structure allowing for trainability may also lead to classical simulability.
13.
Filippo Girardi, Giacomo De Palma
Trained quantum neural networks are Gaussian processes Talk
2024.
Abstract | Tags: Intersection of quantum information and machine learning, Quantum algorithms
@Talk{T24_59,
title = {Trained quantum neural networks are Gaussian processes},
author = {Filippo Girardi and Giacomo De Palma},
year = {2024},
date = {2024-01-01},
abstract = {We study quantum neural networks made by parametric one-qubit gates and fixed two-qubit gates in the limit of infinite width, where the generated function is the expectation value of the sum of single-qubit observables over all the qubits. First, we prove that the probability distribution of the function generated by the untrained network with randomly initialized parameters converges in distribution to a Gaussian process whenever each measured qubit is correlated only with few other measured qubits. Then, we analytically characterize the training of the network via gradient descent with square loss on supervised learning problems. We prove that, as long as the network is not affected by barren plateaus, the trained network can perfectly fit the training set and that the probability distribution of the function generated after training still converges in distribution to a Gaussian process. Finally, we consider the statistical noise of the measurement at the output of the network and prove that a polynomial number of measurements is sufficient for all the previous results to hold and that the network can always be trained in polynomial time.},
keywords = {Intersection of quantum information and machine learning, Quantum algorithms},
pubstate = {published},
tppubtype = {Talk}
}
We study quantum neural networks made by parametric one-qubit gates and fixed two-qubit gates in the limit of infinite width, where the generated function is the expectation value of the sum of single-qubit observables over all the qubits. First, we prove that the probability distribution of the function generated by the untrained network with randomly initialized parameters converges in distribution to a Gaussian process whenever each measured qubit is correlated only with few other measured qubits. Then, we analytically characterize the training of the network via gradient descent with square loss on supervised learning problems. We prove that, as long as the network is not affected by barren plateaus, the trained network can perfectly fit the training set and that the probability distribution of the function generated after training still converges in distribution to a Gaussian process. Finally, we consider the statistical noise of the measurement at the output of the network and prove that a polynomial number of measurements is sufficient for all the previous results to hold and that the network can always be trained in polynomial time.
