Accepted talks

@Talk{T24_234,

title = {(Quantum) complexity of testing signed graph clusterability},

author = {Kuo-Chin Chen and Simon Apers and Min-Hsiu Hsieh},

year  = {2024},

date = {2024-01-01},

abstract = {This study examines clusterability testing for a signed graph in the bounded-degree model. Our contributions are two-fold. First, we provide a quantum algorithm with query complexity $tildeO(N^1/3)$ for testing clusterability, which yields a polynomial speedup over the best classical clusterability tester known [Florian Adriaens and Simon Apers. Testing cluster properties of signed graphs.]. Second, we prove an $tildeØmega(sqrtN)$ classical query lower bound for testing clusterability, which nearly matches the upper bound from citeadriaens2021testing. This settles the classical query complexity of clusterability testing, and it shows that our quantum algorithm has an advantage over any classical algorithm.},

keywords = {Other, Proceedings, Quantum algorithms},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_288,

title = {A Direct Reduction from the Polynomial to the Adversary Method},

author = {Aleksandrs Belovs},

year  = {2024},

date = {2024-01-01},

abstract = {The polynomial and the adversary methods are the two main tools for proving lower bounds on query complexity of quantum algorithms. Both methods have found a large number of applications, some problems more suitable for one method, some for the other. It is known though that the adversary method, in its general negative-weighted version, is tight for bounded-error quantum algorithms, whereas the polynomial method is not. By the tightness of the former, for any polynomial lower bound, there ought to exist a corresponding adversary lower bound. However, direct reduction was not known. In this paper, we give a simple and direct reduction from the polynomial method (in the form of a dual polynomial) to the adversary method. This shows that any lower bound in the form of a dual polynomial is actually an adversary lower bound of a specific form.},

keywords = {Proceedings, Quantum algorithms, Quantum complexity theory},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_325,

title = {A shortcut to a near-optimal quantum linear system solver},

author = {Alexander Dalzell},

year  = {2024},

date = {2024-01-01},

abstract = {Given a linear system of equations Ax = b, quantum linear system solvers (QLSSs) approximately prepare a quantum state |x⟩ for which the amplitudes are proportional to the solution vector x. Asymptotically optimal QLSSs have query complexity O(κlog(1/ε)), where κ is the condition number of A, and ε is the approximation error. However, runtime guarantees for existing optimal and near-optimal QLSSs do not have favorable constant factors, in part because they rely on complex or difficult-to-analyze techniques like variable-time amplitude amplification and adiabatic path-following. Here, we give a conceptually simple, near-optimal QLSS that does not use these techniques. If the solution norm ∥x∥∥A∥/∥b∥ is known exactly, our QLSS requires only a single application of kernel reflection (an extension of eigenstate filtering), and has query complexity (1 + O(ε))κ ln(2√2/ε). If the norm is not known, it can be estimated up to a constant factor using O(log log(κ)) applications of kernel projection (a slight generalization of eigenstate filtering), yielding a QLSS with near-optimal total complexity O(κ log log(κ) log log log(κ) + κ log(1/ε)). Preliminary constant-factor analysis suggests that for practical values of κ, ε our QLSS provides rigorous guarantees that are at least an order of magnitude better than previous guarantees.},

keywords = {Quantum algorithms},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_62,

title = {An improved Quantum Max Cut approximation via Maximum Matching},

author = {Eunou Lee and Ojas Parekh},

year  = {2024},

date = {2024-01-01},

abstract = {Finding a high (or low) energy state of a given quantum Hamiltonian is a potential area to gain a provable and practical quantum advantage. A line of recent studies focuses on Quantum Max Cut, where one is asked to find a high energy state of a given antiferromagnetic Heisenberg Hamiltonian. In this work, we present a classical approximation algorithm for Quantum Max Cut that achieves an approximation ratio of 0.595, outperforming the previous best algorithms of Lee (0.562, generic input graph) and King (0.582, triangle-free input graph). The algorithm is based on finding the maximum weighted matching of an input graph and outputs a product of at most 2-qubit states, which is simpler than the fully entangled output states of the previous best algorithms},

keywords = {Intersection of quantum information and condensed-matter theory, Quantum algorithms},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_137,

title = {Efficient Algorithms for All Port-Based Teleportation Protocols},

author = {Adam Wills and Min-Hsiu Hsieh and Sergii Strelchuk},

year  = {2024},

date = {2024-01-01},

abstract = {We resolve the long-standing open problem of implementing port-based teleportation (PBT) efficiently in all regimes: both probabilistically and deterministically, either with maximally entangled resource state or an optimised resource state. Compared to previous PBT implementations, which are restricted to the deterministic setting, we are able to demonstrate an exponential improvement in the number of ancillas required, as well as polynomial improvements in the gate complexity (albeit in separate protocols). The framework we introduce to implement PBT is flexible enough to be generalisable to other cases of the pretty good measurement, which is useful in the case that the approach via Petz recovery is inefficient.},

keywords = {Quantum algorithms, Quantum information theory},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_423,

title = {Efficient Optimal Control of Open Quantum Systems},

author = {Wenhao He and Tongyang Li and Xiantao Li and Zecheng Li and Chunhao Wang and Ke Wang},

year  = {2024},

date = {2024-01-01},

abstract = {The optimal control problem for open quantum systems can be formulated as a time- dependent Lindbladian that is parameterized by a number of time-dependent control variables. Given an observable and an initial state, the goal is to tune the control variables so that the expected value of some observable with respect to the final state is maximized. In this paper, we present algorithms for solving this optimal control problem efficiently, i.e., having a poly-logarithmic dependency on the system dimension, which is exponentially faster than best-known classical algorithms. Our algorithms are hybrid, consisting of both quantum and classical components. The quantum procedure simulates time-dependent Lindblad evolution that drives the initial state to the final state, and it also provides access to the gradients of the objective function via quantum gradient estimation. The classical procedure uses the gradient information to update the control variables. At the technical level, we provide the first (to the best of our knowledge) simulation al- gorithm for time-dependent Lindbladians with an ℓ1-norm dependence. As an alternative, we also present a simulation algorithm in the interaction picture to improve the algorithm for the cases where the time-independent component of a Lindbladian dominates the time-dependent part. On the classical side, we heavily adapt the state-of-the-art classical optimization analysis to interface with the quantum part of our algorithms. Both the quantum simulation techniques and the classical optimization analyses might be of independent interest},

keywords = {Proceedings, Quantum algorithms, Quantum information theory, Simulation of quantum systems},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_403,

title = {Efficient quantum circuits for port-based teleportation},

author = {Dmitry Grinko and Adam Burchardt and Maris Ozols},

year  = {2024},

date = {2024-01-01},

abstract = {Port-based teleportation (PBT) is a variant of quantum teleportation that, unlike the canonical protocol by Bennett et al., does not require a correction operation on the teleported state. Since its introduction by Ishizaka and Hiroshima in 2008, no efficient implementation of PBT was known. We close this long-standing gap using methods from representation theory, in particular, recent results on representations of partially transposed permutation matrix algebras and mixed quantum Schur transform. We describe efficient quantum circuits for probabilistic and deterministic PBT protocols on n ports of arbitrary local dimension, both for EPR and optimized resource states. We provide two constructions based on different encodings of the so-called Gelfand-Tsetlin basis for n qudits: a standard encoding that achieves O(n) time and O(n log(n)) space complexity, and a Yamanouchi encoding that achieves O(n^2) time and O(log(n)) space complexity, both for constant local dimension and target error. We also describe efficient circuits for preparing the optimal resource states.},

keywords = {Other, Quantum algorithms, Quantum communication, Quantum estimation and measurement, Quantum information theory},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_131,

title = {Efficient Quantum Simulation of Solid-State Materials via Pseudopotentials},

author = {Dominic Berry and Nicholas Rubin and Ahmed Elnabawy and Gabriele Ahlers and Eugene DePrince and Joonho Lee and Christian Gogolin and Ryan Babbush},

year  = {2024},

date = {2024-01-01},

abstract = {First-quantized plane-wave representations provide a very promising approach for quantum algorithms for solid state materials. Pseudopotentials provide a method of further reducing the complexity by avoiding the need to simulate highly localized core orbitals. The complicated functional form of pseudopotentials constitutes a major challenge for the design of quantum algorithms. In this work we provide new techniques to efficiently implement pseudopotentials in quantum algorithms, with orders of magnitude improvement in complexity. Our methods include a high-accuracy QROM interpolation of the exponential function, combined with QROM for the pseudopotential parameters and coherent arithmetic. Moreover, we generalize prior methods to enable the simulation of materials defined by non-cubic unit cells. Finally, we combine these techniques to estimate the resources for block encoding required for simulating commercially relevant instances of heterogeneous catalysis.},

keywords = {Quantum algorithms},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_194,

title = {Eigenpath traversal by Poisson-distributed phase randomisation},

author = {Joseph Cunningham and Jérémie Roland},

year  = {2024},

date = {2024-01-01},

abstract = {We present a framework for quantum computation, similar to Adiabatic Quantum Computation (AQC), that is based on the quantum Zeno effect. By performing randomised dephasing operations at intervals determined by a Poisson process, we are able to track the eigenspace associated to a particular eigenvalue. We derive a simple differential equation for the fidelity leading to general theorems bounding the time complexity of a whole class of algorithms. We also use eigenstate filtering to optimise the scaling of the complexity in the error tolerance ε. In many cases the bounds given by our general theorems are optimal, giving a time complexity of O(1/Δ) with Δ the minimum of the gap. This allows us to prove optimal results using very general features of problems, minimising the amount of problem-specific insight necessary. As two applications of our framework we obtain optimal scaling for the Grover problem (i.e. O(N^1/2) where N is the database size) and the Quantum Linear System Problem (i.e. O(κłog(1/ε)) where κ is the condition number and ε the error tolerance) by direct applications of our theorems.},

keywords = {Models of quantum computation, Proceedings, Quantum algorithms},

pubstate = {published},

tppubtype = {Talk}

}

@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}

}

@Talk{T24_269,

title = {Further improving quantum algorithms for nonlinear differential equations via higher-order methods and rescaling},

author = {Pedro C. S. Costa and Philipp Schleich and Mauro Morales and Dominic W. Berry},

year  = {2024},

date = {2024-01-01},

abstract = {The solution of large systems of nonlinear differential equations is needed for many applications in science and engineering. In this study, we present three main improvements to existing quantum algorithms based on the Carleman linearisation technique. First, by using a high-precision technique for the solution of the linearised differential equations, we achieve logarithmic dependence of the complexity on the error and near-linear dependence on time. Second, we demonstrate that a rescaling technique can considerably reduce the cost, which would otherwise be exponential in the Carleman order for a system of ODEs, preventing a quantum speedup for PDEs. Third, we provide improved, tighter bounds on the error of Carleman linearisation. We show that providing a stability criterion independent of the discretisation can conflict with the use of the rescaling due to the difference between the max-norm and 2-norm.},

keywords = {Quantum algorithms},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_10,

title = {Gapped Clique Homology is QMA1-hard and contained in QMA},

author = {Robbie King and Tamara Kohler},

year  = {2024},

date = {2024-01-01},

abstract = {We study the complexity of a classic problem in computational topology, the homology problem: given a description of some space X and an integer k, decide if X contains a k-dimensional hole. The setting and statement of the homology problem are completely classical, yet we find that the complexity is characterized by quantum complexity classes. Our result can be seen as an aspect of a connection between homology and supersymmetric quantum mechanics [Wit82]. We consider clique complexes, motivated by the practical application of topological data analysis (TDA). The clique complex of a graph is the simplicial complex formed by declaring every k+1-clique in the graph to be a k-simplex. Our main result is that deciding whether the clique complex of a weighted graph has a hole or not, given a suitable promise on the gap, is QMA1-hard and contained in QMA. Our main innovation is a technique to lower bound the eigenvalues of the combinatorial Laplacian operator. For this, we invoke a tool from algebraic topology known as spectral sequences. In particular, we exploit a connection between spectral sequences and Hodge theory [For94]. Spectral sequences will play a role analogous to perturbation theory for combinatorial Laplacians. In addition, we develop the simplicial surgery technique used in prior work [CK22]. Our result provides some suggestion that the quantum TDA algorithm [LGZ16] cannot be dequantized. More broadly, we hope that our results will open up new possibilities for quantum advantage in topological data analysis.},

keywords = {Quantum algorithms, Quantum complexity theory},

pubstate = {published},

tppubtype = {Talk}

}

@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}

}

@Talk{T24_359,

title = {Making both ends meet: from efficient simulation to universal quantum computing with quantum Gibbs sampling},

author = {Daniel Stilck França and Cambyse Rouze and Álvaro Alhambra},

year  = {2024},

date = {2024-01-01},

abstract = {The preparation of thermal states of matter is a crucial task in quantum simulation. In this work, we prove that an efficiently implementable dissipative evolution recently introduced by Chen et al. thermalizes into its equilibrium Gibbs state in time scaling polynomially with system size at high enough temperatures for any Hamiltonian that satisfies a Lieb-Robinson bound, such as local Hamiltonians on a lattice. Furthermore, we show the efficient adiabatic preparation of the associated purifications or ``thermofield double" states. To the best of our knowledge, these are the first results rigorously establishing the efficient preparation of high temperature Gibbs states and their purifications. In the low-temperature regime, we show that implementing this family of Lindbladians for inverse temperatures logarithmic in the system's size is polynomially equivalent to standard quantum computation. On a technical level, for high temperatures, our proof makes use of the mapping of the generator of the evolution into a Hamiltonian and the analysis of the stability of its gap. For low temperature, we instead perform a perturbation at zero temperature of the Laplace transform of the energy observable at fixed runtime, and resort to circuit-to-Hamiltonian mappings akin to the proof of universality of quantum adiabatic computing. Taken together, our results show that the family of Lindbladians of Chen et al. efficiently prepares a large class of quantum many-body states of interest, and have the potential to mirror the success of classical Monte Carlo methods for quantum many-body systems.},

keywords = {Models of quantum computation, Quantum algorithms, Quantum information theory, Simulation of quantum systems},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_381,

title = {Multi-product Hamiltonian simulation with explicit commutator scaling},

author = {Junaid Aftab and Dong An and Konstantina Trivisa},

year  = {2024},

date = {2024-01-01},

abstract = {The multi-product formula (MPF), proposed by [Low, Kliuchnikov, and Wiebe, 2019], is a simple high-order time-independent Hamiltonian simulation algorithm that implements a linear combination of standard product formulas of low order. While the MPF aims to simultaneously exploit commutator scaling among Hamiltonians and achieve near-optimal time and precision dependence, its lack of a rigorous error bound on the nested commutators renders the practical advantage of MPF ambiguous. In this work, we conduct a rigorous complexity analysis of the well-conditioned MPF, demonstrating explicit commutator scaling and near-optimal time and precision dependence at the same time. Using our improved complexity analysis, we present several applications of practical interest where the MPF based on a second-order product formula can achieve a polynomial speedup in both system size and evolution time, as well as an exponential speedup in precision, compared to second-order and even higher-order product formulas. Compared to post-Trotter methods, the MPF based on a second-order product formula can achieve polynomially better scaling in system size, with only poly-logarithmic overhead in evolution time and precision.},

keywords = {Quantum algorithms},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_60,

title = {No distributed quantum advantage for approximate graph coloring},

author = {Xavier Coiteux-Roy and Francesco D'Amore and Rishikesh Gajjala and Fabian Kuhn and Francois Le Gall and Henrik Lievonen and Augusto Modanese and Marc-Olivier Renou and Gustav Schmid and Jukka Suomela},

year  = {2024},

date = {2024-01-01},

abstract = {We give an almost complete characterization of the hardness of $c$-coloring χ-chromatic graphs with distributed algorithms, for a wide range of models of distributed computing. In particular, we show that these problems do not admit any distributed quantum advantage. To do that: beginenumerate ıtem We give a new distributed algorithm that finds a $c$-coloring in χ-chromatic graphs in $tildemathcalO(n^frac1alpha)$ rounds, with $alpha = biglłfloorfracc-1chi - 1bigrrfloor$. ıtem We prove that any distributed algorithm for this problem requires $Ømega(n^frac1alpha)$ rounds. endenumerate Our upper bound holds in the classical, deterministic $mathsfLOCAL$ model, while the near-matching lower bound holds in the emphnon-signaling model. This model, introduced by Arfaoui and Fraigniaud in 2014, captures all models of distributed graph algorithms that obey physical causality; this includes not only classical deterministic $mathsfLOCAL$ and randomized $mathsfLOCAL$ but also $mathsfquantum$-$mathsfLOCAL$, even with a pre-shared quantum state. We also show that similar arguments can be used to prove that, e.g., 3-coloring 2-dimensional grids or $c$-coloring trees remain hard problems even for the non-signaling model, and in particular do not admit any quantum advantage. Our lower-bound arguments are purely graph-theoretic at heart; no background on quantum information theory is needed to establish the proofs.},

keywords = {Models of quantum computation, Quantum algorithms},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_132,

title = {On the Power of Quantum Distributed Proofs},

author = {Atsuya Hasegawa and Srijita Kundu and Harumichi Nishimura},

year  = {2024},

date = {2024-01-01},

abstract = {Quantum nondeterministic distributed computing was recently introduced as $mathsfdQMA$ (distributed quantum Merlin-Arthur) protocols by Fraigniaud, Le Gall, Nishimura and Paz (ITCS 2021). In $mathsfdQMA$ protocols, with the help of quantum proofs and local communication, nodes on a network verify some global property of the network. Fraigniaud et al.~showed that, when the network size is small, there exists an exponential separation in proof size between distributed classical and quantum verification protocols, for the equality problem, where the verifiers check if all the data owned by a subset of them are identical or not. In this paper, we further investigate and characterize the power of the $mathsfdQMA$ protocols for various decision problems. First, we give a more efficient $mathsfdQMA$ protocol for the equality problem with a simpler analysis. This is done by adding a symmetrization step on each node and exploiting properties of the permutation test, which is a generalization of the SWAP test. We also show a quantum advantage for the equality problem on path networks still persists even when the network size is large, by considering ``relay points'' between extreme nodes. Second, we show that even in a general network, there exist efficient $mathsfdQMA$ protocols for the ranking verification problem, the Hamming distance problem, and more problems that derive from efficient quantum one-way communication complexity protocols. Third, in a line network, we construct an efficient $mathsfdQMA$ protocol for a problem that has an efficient two-party $mathsfQMA$ communication complexity protocol. Finally, we obtain the first lower bounds on the proof and communication cost of $mathsfdQMA$ protocols. To prove a lower bound on the equality problem, we show any $mathsfdQMA$ protocol with an entangled proof between nodes can be simulated with a $mathsfdQMA$ protocol with a separable proof between nodes by using a $mathsfQMA$ communication-complete problem introduced by Raz and Shpilka (CCC 2004).},

keywords = {Quantum algorithms, Quantum communication, Quantum complexity theory},

pubstate = {published},

tppubtype = {Talk}

}

@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}

}

@Talk{T24_30,

title = {One Clean Qubit Suffices for Quantum Communication Advantage},

author = {Uma Girish and Srinivasan Arunachalam and Noam Lifshitz},

year  = {2024},

date = {2024-01-01},

abstract = {We study the one-clean-qubit model of quantum communication where one qubit is in a pure state and all other qubits are maximally mixed. We demonstrate a partial function that has a quantum protocol of cost O(log N) in this model, however, every interactive randomized protocol has cost Ømega(sqrtN), settling a conjecture of Klauck and Lim. In contrast, all prior quantum versus classical communication separations required at least Ømega(log N) clean qubits. The function demonstrating our separation also has an efficient protocol in the quantum-simultaneous-with-entanglement model of cost O(log N). We thus recover the state-of-the-art separations between quantum and classical communication complexity. Our proof is based on a recent hypercontractivity inequality introduced by Ellis, Kindler, Lifshitz, and Minzer, in conjunction with tools from the representation theory of compact Lie groups.},

keywords = {Models of quantum computation, Quantum algorithms, Quantum communication, Quantum complexity theory},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_61,

title = {Online Locality Meets Distributed Quantum Computing},

author = {Amirreza Akbari and Xavier Coiteux-Roy and Francesco D'Amore and Francois Le Gall and Henrik Lievonen and Darya Melnyk and Augusto Modanese and Shreyas Pai and Marc-Olivier Renou and Václav Rozhoň and Jukka Suomela},

year  = {2024},

date = {2024-01-01},

abstract = {We extend the theory of locally checkable labeling problems (LCLs) from the classical LOCAL model to a number of other models that have been studied recently, including the quantum-LOCAL model, finitely-dependent processes, non-signaling model, dynamic-LOCAL model, and online-LOCAL model [e.g. STOC 2024, ICALP 2023]. First, we demonstrate the advantage that finitely-dependent processes have over the classical LOCAL model. We show that all LCL problems solvable with locality $O(łog* n)$ in the LOCAL model admit a finitely-dependent distribution (with constant locality). In particular, this gives a finitely-dependent coloring for regular trees, answering an open question by Holroyd [2023]. This also introduces a new formal barrier for understanding the distributed quantum advantage: it is not possible to exclude quantum advantage for any LCL in the $Theta(łog* n)$ complexity class by using non-signaling arguments. Second, we put limits on the capabilities of all of these models. To this end, we introduce a model called randomized online-LOCAL, which is strong enough to simulate e.g. SLOCAL and dynamic-LOCAL, and we show that it is also strong enough to simulate any non-signaling distribution and hence any quantum-LOCAL algorithm. We prove the following result for trees: if we can solve an LCL problem with locality $o(łog^(gapexp) n)$ in the randomized online-LOCAL model, we can solve it with locality $O(łog* n)$ in the classical deterministic LOCAL model. Put together, these results show that in trees the set of LCLs that can be solved with locality $O(łog* n)$ is the same across all these models: locality $O(łog* n)$ in quantum-LOCAL, non-signaling model, dynamic-LOCAL, or online-LOCAL is not stronger than locality $O(łog* n)$ in the classical deterministic LOCAL model.},

keywords = {Models of quantum computation, Quantum algorithms},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_79,

title = {Preparation of Matrix Product States with Log-Depth Quantum Circuits},

author = {Daniel Malz and Georgios Styliaris and Zhi-Yuan Wei and J. Ignacio Cirac},

year  = {2024},

date = {2024-01-01},

abstract = {We consider the preparation of matrix product states (MPS) on quantum devices via quantum circuits of local gates. We first prove that faithfully preparing translation-invariant normal MPS of $N$ sites requires a circuit depth $T=Ømega(łog N)$. We then introduce an algorithm based on the renormalization-group transformation to prepare normal MPS with an error ε in depth $T=O(łog (N/epsilon))$, which is optimal. We also show that measurement and feedback leads to an exponential speedup of the algorithm, to $T=O(łogłog (N/epsilon))$. Measurements also allow one to prepare arbitrary translation-invariant MPS, including long-range non-normal ones, in the same depth. Finally, the algorithm naturally extends to inhomogeneous MPS.},

keywords = {Intersection of quantum information and condensed-matter theory, Quantum algorithms, Quantum information theory},

pubstate = {published},

tppubtype = {Talk}

}

@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}

}

@Talk{T24_45,

title = {Provable Advantage in Quantum PAC Learning},

author = {Wilfred Salmon and Sergii Strelchuk and Tom Gur},

year  = {2024},

date = {2024-01-01},

abstract = {We revisit the problem of characterising the complexity of Quantum PAC learning, as introduced by Bshouty and Jackson [SIAM J. Comput. 1998, 28, 1136–1153]. Several quantum advantages have been demonstrated in this setting, however, none are generic: they apply to particular concept classes and typically only work when the distribution that generates the data is known. In the general case, it was recently shown by Arunachalam and de Wolf [JMLR, 19 (2018) 1-36] that quantum PAC learners can only achieve constant factor advantages over classical PAC learners. We show that with a natural extension of the definition of quantum PAC learning used by Arunachalam and de Wolf, we can achieve a generic advantage in quantum learning. To be precise, for any concept class $mathcalC$ of VC dimension $d$, we show there is an $(epsilon, delta)$-quantum PAC learner with sample complexity [ Ołeft(frac1sqrtepsilonłeft[d+ łog(frac1delta)right]łog^9(1/epsilon)right). ] Up to polylogarithmic factors, this is a square root improvement over the classical learning sample complexity. We show the tightness of our result by proving an $Ømega(d/sqrtepsilon)$ lower bound that matches our upper bound up to polylogarithmic factors.},

keywords = {Quantum algorithms},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_86,

title = {Pseudoentanglement Ain't Cheap},

author = {Sabee Grewal and Vishnu Iyer and William Kretschmer and Daniel Liang},

year  = {2024},

date = {2024-01-01},

abstract = {We show that any pseudoentangled state ensemble with a gap of t bits of entropy requires Ω(t) non-Clifford gates to prepare, matching known lower bounds for pseudorandom state ensembles. Our result follows from a polynomial-time algorithm to estimate the entanglement entropy of a quantum state across any cut of qubits. When run on an n-qubit state that is stabilized by least 2^n-t Pauli operators, our algorithm produces an estimate that is within an additive factor of t/2 bits of the true entanglement entropy.},

keywords = {Quantum algorithms, Quantum complexity theory, Quantum information theory},

pubstate = {published},

tppubtype = {Talk}

}

@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}

}

@Talk{T24_386,

title = {Quantum Circuits surpass Biased Threshold Circuits in Constant-Depth},

author = {Min-Hsiu Hsieh and Leandro Mendes and Michael Oliveira and Sathyawageeswar Subramanian},

year  = {2024},

date = {2024-01-01},

abstract = {Shallow-depth quantum circuits with gates of bounded fan-in have been demonstrated to achieve computational advantages over shallow-depth classical circuits, even allowing for unbounded fan-in (AC0). Despite their versatility, these computational models are known to be less powerful than Polynomial Threshold Function (PTF) circuits, which serve as a natural model for neural networks and exhibit enhanced expressivity and computational capabilities. We prove that PTF circuits with a constant number of layers, when biased (having the activation region of their gates limited), fail to solve certain computational (relational) problems that quantum circuits of constant depth can solve. Furthermore, we prove such a separation for a family of problems, one for each prime qudit dimension. We prove all of these separations via correlation bounds for average-case hardness. We also establish a tight lower bound on the size of biased PTF circuits that can solve a specific relational problem *exactly*. This allows us to significantly reduce the estimated resource requirements for potential demonstrations of quantum advantage. The main challenges in this area of research arise in establishing the classical lower bounds, and in designing non-local games with quantum-classical gaps in the winning strategy in order to go beyond qubits to higher dimensions. To address the former, we have formulated novel switching lemmas specifically designed for multi-output biased PTF circuits, and have developed a way to assess the difficulty of deriving exact solutions. Our contribution towards the latter is grounded in a novel assortment of non-local games, characterized by an exponential difference between their classical and quantum success probabilities. Finally, our technical developments could be of more general and independent interest.},

keywords = {Quantum algorithms, Quantum complexity theory},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_124,

title = {Quantum computation of stopping power for inertial fusion target design},

author = {Nicholas Rubin and Dominic Berry and Alina Kononov and Fionn Malone and Tanuj Khattar and Alec White and Joonho Lee and Hartmut Neven and Ryan Babbush and Andrew Baczewski},

year  = {2024},

date = {2024-01-01},

abstract = {Stopping power is the rate at which a material absorbs the kinetic energy of a charged particle passing through it – one of many properties needed over a wide range of thermodynamic conditions in modeling inertial fusion implosions. First-principles stopping calculations are classically challenging because they involve the dynamics of large electronic systems far from equilibrium, with accuracies that are particularly difficult to constrain and assess in the warm-dense conditions preceding ignition. Here, we describe a protocol for using a fault-tolerant quantum computer to calculate stopping power from a first-quantized representation of the electrons and projectile. Our approach builds upon the electronic structure block encodings of Su et al. [PRX Quantum 2, 040332 2021], adapting and optimizing those algorithms to estimate observables of interest from the non-Born-Oppenheimer dynamics of multiple particle species at finite temperature. We also work out the constant factors associated with a novel implementation of a high-order Trotter approach to simulating a grid representation of these systems. Ultimately, we report logical qubit requirements and leading-order Toffoli costs for computing the stopping power of various projectile/target combinations relevant to interpreting and designing inertial fusion experiments. We estimate that scientifically interesting and classically intractable stopping power calculations can be quantum simulated with roughly the same number of logical qubits and about one hundred times more Toffoli gates than is required for state-of-the-art quantum simulations of industrially relevant molecules such as FeMoco or P450.},

keywords = {Quantum algorithms, Simulation of quantum systems},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_68,

title = {Quantum Generic Hardness for Discrete Logarithms and Integer Factorization},

author = {Minki Hhan and Takashi Yamakawa and Aaram Yun},

year  = {2024},

date = {2024-01-01},

abstract = {We study the quantum computational complexity of the discrete logarithm (DL) problems and integer factorization in the context of ``generic algorithms''—that is, algorithms that do not exploit any properties of the group/ring encoding. We establish the generic models of quantum algorithms for group/ring problems as quantum analogs of their classical counterparts. In these models, we count the number of group/ring operations as complexity measures. Shor's and Regev's algorithms (or their slight modifications) can be described in these models. We show the quantum complexity lower bounds and (almost) matching algorithms of the discrete logarithm and integer factorization in these models. * (The DL problem, fully quantum setting) We prove that any generic quantum DL algorithm must make a logarithmic number of group operations for the group size, showing that Shor's algorithm that makes the logarithmic number of group operations is asymptotically optimal regarding the number of group operations. This holds even considering parallel quantum algorithms. * (The DL problem, hybrid/memory-bounded setting) We observe that some (known) variations of Shor's algorithm can take advantage of classical computations to reduce the number and depth of quantum group operations. We establish a model for generic hybrid quantum-classical algorithms and prove the matching lower bounds. We also study the memory-bounded setting and establish asymptotically tight lower bounds. We extend these results to the multiple-instance DL problem with a matching new algorithm. * (Integer factorization) We give a logarithmic lower bound for the order-finding algorithms, an important step for Shor's algorithm. We also prove a logarithmic lower bound for a certain generic factoring algorithm outputting relatively small integers, which includes a modified version of Regev's algorithm.},

keywords = {Models of quantum computation, Quantum algorithms, Quantum complexity theory},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_281,

title = {Quantum Non-Identical Mean Estimation: Efficient Algorithms and Fundamental Limits},

author = {Jiachen Hu and Tongyang Li and Xinzhao Wang and Yecheng Xue and Chenyi Zhang and Han Zhong},

year  = {2024},

date = {2024-01-01},

abstract = {We systematically investigate quantum algorithms and lower bounds for mean estimation given query access to non-identically distributed samples. On the one hand, we give quantum mean estimators with quadratic quantum speed-up given samples from different bounded or sub-Gaussian random variables. On the other hand, we prove that, in general, it is impossible for any quantum algorithm to achieve quadratic speed-up over the number of classical samples needed to estimate the mean μ, where the samples come from different random variables with mean close to μ. Technically, our quantum algorithms reduce bounded and sub-Gaussian random variables to the Bernoulli case, and use an uncomputation trick to overcome the challenge that direct amplitude estimation does not work with non-identical query access. Our quantum query lower bounds are established by simulating non-identical oracles by parallel oracles, and also by an adversarial method with non-identical oracles. Both results pave the way for proving quantum query lower bounds with non-identical oracles in general, which may be of independent interest.},

keywords = {Proceedings, Quantum algorithms},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_243,

title = {Reversible Pebbling: Parallel Quantum Circuits with Low Amortized Space-Time Complexity},

author = {Jeremiah Blocki and Blake Holman and Seunghoon Lee},

year  = {2024},

date = {2024-01-01},

abstract = {We introduce the parallel reversible pebbling game on directed graphs for constructing parallel quantum circuits that are efficient with respect to amortized space-time complexity (equivalently named cumulative complexity (CC)), a stronger metric than the conventional space-time complexity used for parallel algorithms. Our main result is a mapping from irreversible algorithms for computing a function, to quantum algorithms for computing the function in superposition, with just a sub-polynomial overhead in cumulative complexity. Thus, to construct a CC-efficient quantum oracle for a function, it suffices to solve the simpler problem of designing a CC-efficient classical algorithm for the function. This transformation also allows us to leverage the vast body of work on classical pebbling games for developing parallel quantum circuits with low amortized space-time complexity, given the data-dependency graph of the problem.},

keywords = {Quantum algorithms, Quantum complexity theory, Quantum cryptography},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_110,

title = {Reversing Unknown Quantum Processes via Virtual Combs: for Channels with Limited Information},

author = {Chengkai Zhu and Yin Mo and Yu-Ao Chen and Xin Wang},

year  = {2024},

date = {2024-01-01},

abstract = {The inherent irreversibility of quantum dynamics for open systems poses a significant barrier to the inversion of unknown quantum processes. To tackle this challenge, we propose the framework of virtual combs that exploit the unknown process iteratively with additional classical post-processing to simulate the process inverse. Notably, we demonstrate that an $n$-slot virtual comb can exactly reverse a depolarizing channel with one unknown noise parameter out of $n+1$ potential candidates, and a 1-slot virtual comb can exactly reverse an arbitrary pair of quantum channels. We further explore the approximate inversion of an unknown channel within a given channel set. A worst-case error decay of $cO(n^-1)$ is unveiled for depolarizing channels within a specified noise region. Moreover, we show that virtual combs can universally reverse unitary operations and investigate the trade-off between the slot number and the sampling overhead.},

keywords = {Quantum algorithms, Quantum information theory},

pubstate = {published},

tppubtype = {Talk}

}

@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}

}

@Talk{T24_464,

title = {State Purification with Symmetry Subgroup Projectors},

author = {Bo Yang and Elham Kashefi and Dominik Leichtle and Harold Ollivier},

year  = {2024},

date = {2024-01-01},

abstract = {Quantum state purification is the functionality that, given multiple copies of an unknown state, outputs a state with increased purity. This is an essential building block for the near- and middle-term quantum ecosystems before the availability of full fault tolerance, where one may want to obtain purified quantum states instead of expectation values. We propose an effective state purification gadget with a moderate quantum overhead by projecting multiple noisy quantum inputs to their symmetry subspace defined by a set of projectors forming a subgroup of the symmetry group. This provides a state purification performance scaling inverse-linearly to the number of state copies given a fixed stochastic error rate, which drastically improves the implementation overhead in previous works. Our method may find its application in designing robust verification protocols for quantum outputs before the availability of fully fault-tolerant computing.},

keywords = {Quantum algorithms, Quantum information theory},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_317,

title = {Taming Quantum Time Complexity},

author = {Aleksandrs Belovs and Stacey Jeffery and Duyal Yolcu},

year  = {2024},

date = {2024-01-01},

abstract = {Quantum query complexity has several nice properties with respect to composition. First, bounded-error quantum query algorithms can be composed without incurring log factors through error reduction (emphexactness). Second, through careful accounting (emphthriftiness), the total query complexity is smaller if subroutines are mostly run on cheaper inputs – a property that is much less obvious in quantum algorithms than in their classical counterparts. While these properties were previously seen through the model of span programs (alternatively, the dual adversary bound), a recent work by two of the authors (Belovs, Yolcu 2023) showed how to achieve these benefits without converting to span programs, by defining emphquantum Las Vegas query complexity. Independently, recent works, including by one of the authors (Jeffery 2022), have worked towards bringing thriftiness to the more practically significant setting of quantum emphtime complexity. In this work, we show how to achieve both exactness and thriftiness in the setting of time complexity. We generalize the quantum subroutine composition results of Jeffery 2022 so that, in particular, no error reduction is needed. We give a time complexity version of the well-known result in quantum query complexity, $Q(fcirc g)=ØO(Q(f)cdot Q(g))$, without log factors. We achieve this by employing a novel approach to the design of quantum algorithms based on what we call emphtransducers, and which we think is of large independent interest. While a span program is a completely different computational model, a transducer is a direct generalisation of a quantum algorithm, which allows for much greater transparency and control. Transducers naturally characterize general state conversion, rather than only decision problems; provide a very simple treatment of other quantum primitives such as quantum walks; and lend themselves well to time complexity analysis.},

keywords = {Quantum algorithms},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_222,

title = {The Quantum Decoding Problem},

author = {André Chailloux and Jean-Pierre Tillich},

year  = {2024},

date = {2024-01-01},

abstract = {One of the founding results of lattice based cryptography is a quantum reduction from the Short Integer Solution (SIS) problem to the Learning with Errors (LWE) problem introduced by Regev. It has recently been pointed out by Chen, Liu and Zhandry[CLZ22] that this reduction can be made more powerful by replacing the LWE problem with a quantum equivalent, where the errors are given in quantum superposition. In parallel, Regev's reduction has recently been adapted in the context of code-based cryptography by Debris, Remaud and Tillich[DRT23], who showed a reduction between the Short Codeword Problem and the Decoding Problem (the DRT reduction). This motivates the study of the Quantum Decoding Problem (QDP), which is the Decoding Problem but with errors in quantum superposition and see how it behaves in the DRT reduction. The purpose of this paper is to introduce and to lay a firm foundation for QDP. We first show QD Pis likely to be easier than classical decoding, by proving that it can be solved in quantum polynomial time in a large regime of noise whereas no non-exponential quantum algorithm is known for the classical decoding problem. Then, we show that QDP can even be solved (albeit not necessarily efficiently) beyond the information theoretic Shannon limit for classical decoding. We give precisely the largest noise level where we can solve QDP giving in a sense the information theoretic limit for this new problem. Finally, we study how QDP can be used in the DRT reduction. First, we show that our algorithms can be properly used in the DRT reduction showing that our quantum algorithms for QDP beyond Shannon capacity can be used to find minimal weight codewords in a random code. On the negative side, we show that the DRT reduction cannot be, in all generality, a reduction between finding small codewords and QDP by exhibiting quantum algorithms for QDP where this reduction entirely fails. Our proof techniques include the use of specific quantum measurements, such as q-ary unambiguous state discrimination and pretty good measurements as well as strong concentration bounds on weight distribution of random shifted dual codes, which we relate using quantum Fourier analysis.},

keywords = {Proceedings, Quantum algorithms, Quantum information theory},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_431,

title = {The Quantum Esscher Transform},

author = {Yixian Qiu and Kelvin Koor and Patrick Rebentrost},

year  = {2024},

date = {2024-01-01},

abstract = {The Esscher Transform is a tool of broad utility in various domains of applied probability. It provides the solution to a constrained minimum relative entropy optimization problem. In this work, we study the generalization of the Esscher Transform to the quantum setting. We examine a relative entropy minimization problem for a quantum density operator, potentially of wide relevance in quantum information theory. The resulting solution form motivates us to define the quantum Esscher Transform, which subsumes the classical Esscher Transform as a special case. Envisioning potential applications of the quantum Esscher Transform, we also discuss its implementation on fault-tolerant quantum computers. Our algorithm is based on the modern techniques of block-encoding and quantum singular value transformation (QSVT). We show that given block-encoded inputs, our algorithm outputs a subnormalized block-encoding of the quantum Esscher transform within accuracy ε in $tilde O(kappa d łog^2 1/epsilon)$ queries to the inputs, where κ is the condition number of the input density operator and $d$ is the number of constraints.},

keywords = {Quantum algorithms, Quantum information theory},

pubstate = {published},

tppubtype = {Talk}

}

@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}

}

@Talk{T24_316,

title = {Virtual Channel Purification},

author = {Zhenhuan Liu and Xingjian Zhang and Yue-Yang Fei and Zhenyu Cai},

year  = {2024},

date = {2024-01-01},

abstract = {Quantum error mitigation is a key approach for extracting target state properties on state-of-the-art noisy machines and early fault-tolerant devices. Using the ideas from flag fault tolerance and virtual state purification, we develop the virtual channel purification (VCP) protocol, which consumes similar qubit and gate resources as virtual state purification but offers up to exponentially stronger error suppression with increased system size and more noisy operation copies. Furthermore, VCP removes most of the assumptions required in virtual state purification. Essentially, VCP is the first quantum error mitigation protocol that does not require specific knowledge about the noise models, the target quantum state, and the target problem while still offering rigorous performance guarantees for practical noise regimes. Further connections are made between VCP and quantum error correction to produce one of the first protocols that combine quantum error correction and quantum error mitigation beyond concatenation. We can remove all noise in the channel while paying only the same sampling cost as low-order purification, reaching beyond the standard bias-variance trade-off in quantum error mitigation. Our protocol can also be adapted to key tasks in quantum networks like channel capacity activation and entanglement distribution.},

keywords = {Quantum algorithms, Quantum error correction and fault-tolerant quantum computing},

pubstate = {published},

tppubtype = {Talk}

}