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.
Paul Gondolf, Samuel O. Scalet, Alberto Ruiz-de-Alarcón, Álvaro M. Alhambra, Ángela Capel
Conditional independence of 1D Gibbs states with applications to efficient learning Talk
2024.
Abstract | Tags: Intersection of quantum information and condensed-matter theory, Quantum estimation and measurement, Quantum information theory
@Talk{T24_298,
title = {Conditional independence of 1D Gibbs states with applications to efficient learning},
author = {Paul Gondolf and Samuel O. Scalet and Alberto Ruiz-de-Alarcón and Álvaro M. Alhambra and Ángela Capel},
year = {2024},
date = {2024-01-01},
abstract = {We show that spin chains in thermal equilibrium have a correlation structure in which individual regions are strongly correlated at most with their near vicinity. We quantify this with alternative notions of the conditional mutual information defined through the so-called Belavkin-Staszewski relative entropy. Our main result is the superexponential decay of various such measures, under the assumption that the spin chain Hamiltonian is translation-invariant. We use a recovery map associated with these definitions to sequentially construct tensor network approximations in terms of marginals of small (sub-logarithmic) size. This allows for representations of the state that can be learned efficiently from local measurements. We also prove an approximate factorization condition for the purity, from which it follows that the purity of the entire Gibbs state can be efficiently estimated to a small multiplicative error. As a technical step of independent interest, we show an upper bound to the decay of the Belavkin-Staszewski relative entropy upon the application of a conditional expectation.},
keywords = {Intersection of quantum information and condensed-matter theory, Quantum estimation and measurement, Quantum information theory},
pubstate = {published},
tppubtype = {Talk}
}
We show that spin chains in thermal equilibrium have a correlation structure in which individual regions are strongly correlated at most with their near vicinity. We quantify this with alternative notions of the conditional mutual information defined through the so-called Belavkin-Staszewski relative entropy. Our main result is the superexponential decay of various such measures, under the assumption that the spin chain Hamiltonian is translation-invariant. We use a recovery map associated with these definitions to sequentially construct tensor network approximations in terms of marginals of small (sub-logarithmic) size. This allows for representations of the state that can be learned efficiently from local measurements. We also prove an approximate factorization condition for the purity, from which it follows that the purity of the entire Gibbs state can be efficiently estimated to a small multiplicative error. As a technical step of independent interest, we show an upper bound to the decay of the Belavkin-Staszewski relative entropy upon the application of a conditional expectation.
2.
Adam Wills, Min-Hsiu Hsieh, Sergii Strelchuk
Efficient Algorithms for All Port-Based Teleportation Protocols Talk
2024.
Abstract | Tags: Quantum algorithms, Quantum information theory
@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}
}
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.
3.
Wenhao He, Tongyang Li, Xiantao Li, Zecheng Li, Chunhao Wang, Ke Wang
Efficient Optimal Control of Open Quantum Systems Talk
2024.
Abstract | Tags: Proceedings, Quantum algorithms, Quantum information theory, Simulation of quantum systems
@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}
}
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
4.
Dmitry Grinko, Adam Burchardt, Maris Ozols
Efficient quantum circuits for port-based teleportation Talk
2024.
Abstract | Tags: Other, Quantum algorithms, Quantum communication, Quantum estimation and measurement, Quantum information theory
@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}
}
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.
5.
Amir Arqand, Thomas Hahn, Ernest Y. -Z. Tan
Generalized Rényi entropy accumulation theorem and generalized quantum probability estimation Talk
2024.
Abstract | Tags: Quantum cryptography, Quantum information theory
@Talk{T24_380,
title = {Generalized Rényi entropy accumulation theorem and generalized quantum probability estimation},
author = {Amir Arqand and Thomas Hahn and Ernest Y. -Z. Tan},
year = {2024},
date = {2024-01-01},
abstract = {The entropy accumulation theorem, and its subsequent generalized version, is a powerful tool in the security analysis of many device-dependent and device-independent cryptography protocols. However, it has the drawback that the finite-size bounds it yields are not necessarily optimal, and furthermore, it relies on the construction of an affine min-tradeoff function, which in practice can often be challenging to construct optimally. In this work, we address both of these challenges simultaneously by deriving a new entropy-accumulation bound. Our bound yields significantly better finite-size performance, and can be computed as a convex optimization without any specification of affine min-tradeoff functions. Furthermore, it can be applied directly at the level of Rényi entropies if desired, yielding fully-Rényi security proofs. Our proof techniques are based on elaborating on a connection between entropy accumulation and the framework of quantum probability estimation, and in the process we obtain some new results with respect to the latter framework as well.},
keywords = {Quantum cryptography, Quantum information theory},
pubstate = {published},
tppubtype = {Talk}
}
The entropy accumulation theorem, and its subsequent generalized version, is a powerful tool in the security analysis of many device-dependent and device-independent cryptography protocols. However, it has the drawback that the finite-size bounds it yields are not necessarily optimal, and furthermore, it relies on the construction of an affine min-tradeoff function, which in practice can often be challenging to construct optimally. In this work, we address both of these challenges simultaneously by deriving a new entropy-accumulation bound. Our bound yields significantly better finite-size performance, and can be computed as a convex optimization without any specification of affine min-tradeoff functions. Furthermore, it can be applied directly at the level of Rényi entropies if desired, yielding fully-Rényi security proofs. Our proof techniques are based on elaborating on a connection between entropy accumulation and the framework of quantum probability estimation, and in the process we obtain some new results with respect to the latter framework as well.
6.
Sergey Bravyi, Natalie Parham, Minh Tran
Identity check problem for shallow quantum circuits Talk
2024.
Abstract | Tags: Other, Quantum information theory, Simulation of quantum systems
@Talk{T24_233,
title = {Identity check problem for shallow quantum circuits},
author = {Sergey Bravyi and Natalie Parham and Minh Tran},
year = {2024},
date = {2024-01-01},
abstract = {Checking whether two quantum circuits are approximately equivalent is a common task in quantum computing. We consider a closely related identity check problem: given a quantum circuit $U$, one has to estimate the diamond-norm distance between $U$ and the identity channel. We present a classical algorithm approximating the distance to the identity within a factor $alpha=D+1$ for shallow geometrically local $D$-dimensional circuits provided that the circuit is sufficiently close to the identity. The runtime of the algorithm scales linearly with the number of qubits for any constant circuit depth and spatial dimension. We also show that the operator-norm distance to the identity $|U-I|$ can be efficiently approximated within a factor $alpha=5$ for shallow 1D circuits and, under a certain technical condition, within a factor $alpha=2D+3$ for shallow $D$-dimensional circuits. A numerical implementation of the identity check algorithm is reported for 1D Trotter circuits with up to 100 qubits.},
keywords = {Other, Quantum information theory, Simulation of quantum systems},
pubstate = {published},
tppubtype = {Talk}
}
Checking whether two quantum circuits are approximately equivalent is a common task in quantum computing. We consider a closely related identity check problem: given a quantum circuit $U$, one has to estimate the diamond-norm distance between $U$ and the identity channel. We present a classical algorithm approximating the distance to the identity within a factor $alpha=D+1$ for shallow geometrically local $D$-dimensional circuits provided that the circuit is sufficiently close to the identity. The runtime of the algorithm scales linearly with the number of qubits for any constant circuit depth and spatial dimension. We also show that the operator-norm distance to the identity $|U-I|$ can be efficiently approximated within a factor $alpha=5$ for shallow 1D circuits and, under a certain technical condition, within a factor $alpha=2D+3$ for shallow $D$-dimensional circuits. A numerical implementation of the identity check algorithm is reported for 1D Trotter circuits with up to 100 qubits.
7.
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.
8.
Sisi Zhou
Limits of noisy quantum metrology with restricted quantum controls Talk
2024.
Abstract | Tags: Quantum estimation and measurement, Quantum information theory
@Talk{T24_81,
title = {Limits of noisy quantum metrology with restricted quantum controls},
author = {Sisi Zhou},
year = {2024},
date = {2024-01-01},
abstract = {The Heisenberg limit (HL) and the standard quantum limit (SQL) are two quantum metrological limits, which describe the scalings of estimation precision $Delta hatþeta$ of an unknown parameter θ with respect to $n$, the number of one-parameter quantum channels applied. It was known that the HL ($Delta hatþeta propto 1/n$) is achievable using quantum error correction (QEC) strategies when the ``Hamiltonian-not-in-Kraus-span'' (HNKS) condition is satisfied; and when HNKS is violated, the SQL ($Delta hatþeta propto 1/n^1/2$) is optimal and can be achieved with $n$ repetitive measurements. However, it is unknown whether such limits are still achievable using restricted quantum devices where the required QEC operations are not available—e.g., finite-size devices where only unitary controls are available or where noiseless ancilla is not available. In this work, we identify various new noisy metrological limits for estimating one-parameter qubit channels in different settings with restricted controls. The HL is proven to be unattainbale in these cases, indicating the necessity of QEC in achieving the HL. Furthermore, we find a necessary and sufficient condition for qubit channels to attain the SQL, called the ``rotation-generators-not-in-Kraus-span'' (RGNKS) condition. When RGNKS is satisfied, the SQL is achievable using only unitary controls and a single measurement. When RGNKS is violated, the estimation precision (in most cases) has a constant floor when repetitive measurements are not allowed. Demonstration of this separation in metrological powers is within reach of current quantum technologies.},
keywords = {Quantum estimation and measurement, Quantum information theory},
pubstate = {published},
tppubtype = {Talk}
}
The Heisenberg limit (HL) and the standard quantum limit (SQL) are two quantum metrological limits, which describe the scalings of estimation precision $Delta hatþeta$ of an unknown parameter θ with respect to $n$, the number of one-parameter quantum channels applied. It was known that the HL ($Delta hatþeta propto 1/n$) is achievable using quantum error correction (QEC) strategies when the ``Hamiltonian-not-in-Kraus-span'' (HNKS) condition is satisfied; and when HNKS is violated, the SQL ($Delta hatþeta propto 1/n^1/2$) is optimal and can be achieved with $n$ repetitive measurements. However, it is unknown whether such limits are still achievable using restricted quantum devices where the required QEC operations are not available—e.g., finite-size devices where only unitary controls are available or where noiseless ancilla is not available. In this work, we identify various new noisy metrological limits for estimating one-parameter qubit channels in different settings with restricted controls. The HL is proven to be unattainbale in these cases, indicating the necessity of QEC in achieving the HL. Furthermore, we find a necessary and sufficient condition for qubit channels to attain the SQL, called the ``rotation-generators-not-in-Kraus-span'' (RGNKS) condition. When RGNKS is satisfied, the SQL is achievable using only unitary controls and a single measurement. When RGNKS is violated, the estimation precision (in most cases) has a constant floor when repetitive measurements are not allowed. Demonstration of this separation in metrological powers is within reach of current quantum technologies.
9.
Shivan Mittal, Nicholas Hunter-Jones
Local random quantum circuits form approximate designs on arbitrary architectures Talk
2024.
Abstract | Tags: Intersection of quantum information and condensed-matter theory, Models of quantum computation, Quantum information theory
@Talk{T24_309,
title = {Local random quantum circuits form approximate designs on arbitrary architectures},
author = {Shivan Mittal and Nicholas Hunter-Jones},
year = {2024},
date = {2024-01-01},
abstract = {We consider random quantum circuits (RQC) on arbitrary connected graphs whose edges determine the allowed 2-qudit interactions. Prior work has established that such $n$-qudit circuits with local dimension $q$ on 1D, complete, and $D$-dimensional graphs form approximate unitary designs, that is, they generate unitaries from distributions close to the Haar measure on the unitary group $U(q^n)$ after polynomially many gates. Here, we extend those results by proving that RQCs comprised of $O(poly(n,k))$ gates on a wide class of graphs form approximate unitary $k$-designs. We prove that RQCs on graphs with spanning trees of bounded degree and height form $k$-designs after $O(|E|n rm poly(k))$ gates, where $|E|$ is the number of edges in the graph. Furthermore, we identify larger classes of graphs for which RQCs generate approximate designs in polynomial circuit size. For $k łeq 4$, we show that RQCs on graphs of certain maximum degrees form designs after $O(|E|n)$ gates, providing explicit constants. We determine our circuit size bounds from the spectral gaps of local Hamiltonians. To that end, we extend the finite-size (or Knabe) method for bounding gaps of frustration-free Hamiltonians on regular graphs to arbitrary connected graphs. We further introduce a new method based on the Detectability Lemma for determining the spectral gaps of Hamiltonians on arbitrary graphs. Our methods have wider applicability as the first method provides a succinct alternative proof of [Commun. Math. Phys. 291, 257 (2009)] and the second method proves that RQCs on any connected architecture form approximate designs in quasi-polynomial circuit size.},
keywords = {Intersection of quantum information and condensed-matter theory, Models of quantum computation, Quantum information theory},
pubstate = {published},
tppubtype = {Talk}
}
We consider random quantum circuits (RQC) on arbitrary connected graphs whose edges determine the allowed 2-qudit interactions. Prior work has established that such $n$-qudit circuits with local dimension $q$ on 1D, complete, and $D$-dimensional graphs form approximate unitary designs, that is, they generate unitaries from distributions close to the Haar measure on the unitary group $U(q^n)$ after polynomially many gates. Here, we extend those results by proving that RQCs comprised of $O(poly(n,k))$ gates on a wide class of graphs form approximate unitary $k$-designs. We prove that RQCs on graphs with spanning trees of bounded degree and height form $k$-designs after $O(|E|n rm poly(k))$ gates, where $|E|$ is the number of edges in the graph. Furthermore, we identify larger classes of graphs for which RQCs generate approximate designs in polynomial circuit size. For $k łeq 4$, we show that RQCs on graphs of certain maximum degrees form designs after $O(|E|n)$ gates, providing explicit constants. We determine our circuit size bounds from the spectral gaps of local Hamiltonians. To that end, we extend the finite-size (or Knabe) method for bounding gaps of frustration-free Hamiltonians on regular graphs to arbitrary connected graphs. We further introduce a new method based on the Detectability Lemma for determining the spectral gaps of Hamiltonians on arbitrary graphs. Our methods have wider applicability as the first method provides a succinct alternative proof of [Commun. Math. Phys. 291, 257 (2009)] and the second method proves that RQCs on any connected architecture form approximate designs in quasi-polynomial circuit size.
10.
Daniel Stilck França, Cambyse Rouze, Álvaro Alhambra
Making both ends meet: from efficient simulation to universal quantum computing with quantum Gibbs sampling Talk
2024.
Abstract | Tags: Models of quantum computation, Quantum algorithms, Quantum information theory, Simulation of quantum systems
@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}
}
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.
11.
Zhili Chen, Joshua A. Grochow, Youming Qiao, Gang Tang, Chuanqi Zhang
Multipartite to tripartite reductions for LU and SLOCC equivalences Talk
2024.
Abstract | Tags: Quantum complexity theory, Quantum information theory
@Talk{T24_23,
title = {Multipartite to tripartite reductions for LU and SLOCC equivalences},
author = {Zhili Chen and Joshua A. Grochow and Youming Qiao and Gang Tang and Chuanqi Zhang},
year = {2024},
date = {2024-01-01},
abstract = {We show that classifying LU and SLOCC equivalences of d-partite pure states can be reduced to classifying such equivalences for tripartite pure states. To this end, we employ techniques from various areas, including path algebras from representation theory of associative algebras, and gadget constructions from computational complexity theory.},
keywords = {Quantum complexity theory, Quantum information theory},
pubstate = {published},
tppubtype = {Talk}
}
We show that classifying LU and SLOCC equivalences of d-partite pure states can be reduced to classifying such equivalences for tripartite pure states. To this end, we employ techniques from various areas, including path algebras from representation theory of associative algebras, and gadget constructions from computational complexity theory.
12.
Harry Buhrman, Dmitry Grinko, Philip Verduyn Lunel, Jordi Weggemans
Permutation tests for quantum state identity Talk
2024.
Abstract | Tags: Other, Quantum estimation and measurement, Quantum information theory
@Talk{T24_400,
title = {Permutation tests for quantum state identity},
author = {Harry Buhrman and Dmitry Grinko and Philip Verduyn Lunel and Jordi Weggemans},
year = {2024},
date = {2024-01-01},
abstract = {The quantum analogue of the equality function, known as the quantum state identity problem, is the task of deciding whether n unknown quantum states are equal or unequal, given the promise that all states are either pairwise orthogonal or identical. Under the one-sided error requirement, it is known that the permutation test is optimal for this task, and for two input states this coincides with the well-known Swap test. Until now, the optimal measurement in the general two-sided error regime was unknown. Under more specific promises, the problem can be solved approximately or even optimally with simpler tests, such as the circle test. This work attempts to capture the underlying structure of (fine-grained formulations of) the quantum state identity problem. Using tools from semi-definite programming and representation theory, we (i) give an optimal test for any input distribution without the one-sided error requirement by writing the problem as an SDP, giving the exact solutions to the primal and dual programs and showing that the two values coincide; (ii) propose a general G-test which uses an arbitrary subgroup G of S_n, giving an analytic expression of the performance of the specific test, and (iii) give an approximation of the permutation test using only a classical permutation and n-1 Swap tests.},
keywords = {Other, Quantum estimation and measurement, Quantum information theory},
pubstate = {published},
tppubtype = {Talk}
}
The quantum analogue of the equality function, known as the quantum state identity problem, is the task of deciding whether n unknown quantum states are equal or unequal, given the promise that all states are either pairwise orthogonal or identical. Under the one-sided error requirement, it is known that the permutation test is optimal for this task, and for two input states this coincides with the well-known Swap test. Until now, the optimal measurement in the general two-sided error regime was unknown. Under more specific promises, the problem can be solved approximately or even optimally with simpler tests, such as the circle test. This work attempts to capture the underlying structure of (fine-grained formulations of) the quantum state identity problem. Using tools from semi-definite programming and representation theory, we (i) give an optimal test for any input distribution without the one-sided error requirement by writing the problem as an SDP, giving the exact solutions to the primal and dual programs and showing that the two values coincide; (ii) propose a general G-test which uses an arbitrary subgroup G of S_n, giving an analytic expression of the performance of the specific test, and (iii) give an approximation of the permutation test using only a classical permutation and n-1 Swap tests.
13.
Daniel Malz, Georgios Styliaris, Zhi-Yuan Wei, J. Ignacio Cirac
Preparation of Matrix Product States with Log-Depth Quantum Circuits Talk
2024.
Abstract | Tags: Intersection of quantum information and condensed-matter theory, Quantum algorithms, Quantum information theory
@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}
}
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.
14.
Sabee Grewal, Vishnu Iyer, William Kretschmer, Daniel Liang
Pseudoentanglement Ain't Cheap Talk
2024.
Abstract | Tags: Quantum algorithms, Quantum complexity theory, Quantum information theory
@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}
}
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.
15.
Tobias Haug, Kishor Bharti, Dax Koh
Pseudorandom unitaries are neither real nor sparse nor noise-robust Talk
2024.
Abstract | Tags: Quantum complexity theory, Quantum cryptography, Quantum estimation and measurement, Quantum information theory
@Talk{T24_71,
title = {Pseudorandom unitaries are neither real nor sparse nor noise-robust},
author = {Tobias Haug and Kishor Bharti and Dax Koh},
year = {2024},
date = {2024-01-01},
abstract = {Pseudorandom quantum states (PRSs) and pseudorandom unitaries (PRUs) possess the dual nature of being efficiently constructible while appearing completely random to any efficient quantum algorithm. In this study, we establish fundamental bounds on pseudorandomness. We show that PRSs and PRUs exist only when the probability that an error occurs is negligible, ruling out their generation on noisy intermediate-scale and early fault-tolerant quantum computers. Additionally, we derive lower bounds on the imaginarity and coherence of PRSs and PRUs, rule out the existence of sparse or real PRUs. We also show that the notions of PRS, PRUs and pseudorandom scramblers (PRSSs) are distinct in terms of resource requirements. We introduce the concept of pseudoresources, where states which contain a low amount of a given resource masquerade as high-resource states. We define pseudocoherence, pseudopurity and pseudoimaginarity, and identify three distinct types of pseudoresources in terms of their masquerading capabilities. Our work also establishes rigorous bounds on the efficiency of property testing, demonstrating the exponential complexity in distinguishing real quantum states from imaginary ones, in contrast to the efficient measurability of unitary imaginarity. Lastly, we show that the transformation from a complex to a real model of quantum computation is inefficient, in contrast to the reverse process, which is efficient. Our results establish fundamental limits on property testing and provide valuable insights into quantum pseudorandomness.},
keywords = {Quantum complexity theory, Quantum cryptography, Quantum estimation and measurement, Quantum information theory},
pubstate = {published},
tppubtype = {Talk}
}
Pseudorandom quantum states (PRSs) and pseudorandom unitaries (PRUs) possess the dual nature of being efficiently constructible while appearing completely random to any efficient quantum algorithm. In this study, we establish fundamental bounds on pseudorandomness. We show that PRSs and PRUs exist only when the probability that an error occurs is negligible, ruling out their generation on noisy intermediate-scale and early fault-tolerant quantum computers. Additionally, we derive lower bounds on the imaginarity and coherence of PRSs and PRUs, rule out the existence of sparse or real PRUs. We also show that the notions of PRS, PRUs and pseudorandom scramblers (PRSSs) are distinct in terms of resource requirements. We introduce the concept of pseudoresources, where states which contain a low amount of a given resource masquerade as high-resource states. We define pseudocoherence, pseudopurity and pseudoimaginarity, and identify three distinct types of pseudoresources in terms of their masquerading capabilities. Our work also establishes rigorous bounds on the efficiency of property testing, demonstrating the exponential complexity in distinguishing real quantum states from imaginary ones, in contrast to the efficient measurability of unitary imaginarity. Lastly, we show that the transformation from a complex to a real model of quantum computation is inefficient, in contrast to the reverse process, which is efficient. Our results establish fundamental limits on property testing and provide valuable insights into quantum pseudorandomness.
16.
Francesco Anna Mele, Farzin Salek, Vittorio Giovannetti, Ludovico Lami
Quantum communication on the bosonic loss-dephasing channel Talk
2024.
Abstract | Tags: Quantum communication, Quantum information theory
@Talk{T24_47,
title = {Quantum communication on the bosonic loss-dephasing channel},
author = {Francesco Anna Mele and Farzin Salek and Vittorio Giovannetti and Ludovico Lami},
year = {2024},
date = {2024-01-01},
abstract = {Quantum optical systems are typically affected by two types of noise: photon loss and dephasing. Despite extensive research on each noise process individually, a comprehensive understanding of their combined effect is still lacking. A crucial problem lies in determining the values of loss and dephasing for which the resulting loss-dephasing channel is anti-degradable, implying the absence of codes capable of correcting its effect or, alternatively, capable of enabling quantum communication. A conjecture in [Quantum 6, 821 (2022)] suggested that the bosonic loss-dephasing channel is anti-degradable if and only if the loss is above 50%. In this paper we refute this conjecture, specifically proving that for any value of the loss, if the dephasing is above a critical value, then the bosonic loss-dephasing channel is anti-degradable. While our result identifies a large parameter region where quantum communication is not possible, we also prove that if two-way classical communication is available, then quantum communication — and thus quantum key distribution — is always achievable, even for high values of loss and dephasing.},
keywords = {Quantum communication, Quantum information theory},
pubstate = {published},
tppubtype = {Talk}
}
Quantum optical systems are typically affected by two types of noise: photon loss and dephasing. Despite extensive research on each noise process individually, a comprehensive understanding of their combined effect is still lacking. A crucial problem lies in determining the values of loss and dephasing for which the resulting loss-dephasing channel is anti-degradable, implying the absence of codes capable of correcting its effect or, alternatively, capable of enabling quantum communication. A conjecture in [Quantum 6, 821 (2022)] suggested that the bosonic loss-dephasing channel is anti-degradable if and only if the loss is above 50%. In this paper we refute this conjecture, specifically proving that for any value of the loss, if the dephasing is above a critical value, then the bosonic loss-dephasing channel is anti-degradable. While our result identifies a large parameter region where quantum communication is not possible, we also prove that if two-way classical communication is available, then quantum communication — and thus quantum key distribution — is always achievable, even for high values of loss and dephasing.
17.
Francesco Anna Mele, Salvatore F. E. Oliviero, Lennart Bittel, Jens Eisert, Vittorio Giovannetti, Ludovico Lami, Lorenzo Leone, Antonio Anna Mele
Quantum state tomography of continuous variable systems Talk
2024.
Abstract | Tags: Quantum information theory
@Talk{T24_237,
title = {Quantum state tomography of continuous variable systems},
author = {Francesco Anna Mele and Salvatore F. E. Oliviero and Lennart Bittel and Jens Eisert and Vittorio Giovannetti and Ludovico Lami and Lorenzo Leone and Antonio Anna Mele},
year = {2024},
date = {2024-01-01},
abstract = {While quantum state tomography has been extensively analysed for qubit and qudit systems, rigorous performance guarantees in terms of ε-approximation in trace distance remain largely unexplored for continuous variable quantum systems, due to subtleties that arise in the infinite-dimensional context. This work addresses this gap. First, we discover that to learn energy-constrained n-mode states, the sample complexity must scale with ε as Ω(1/ε^(2n)). This is in sharp contrast with the n-qubit case, where the ε-scaling is O(1/ε^2) — thereby establishing the extreme inefficiency of continuous variable tomography. Remarkably, we prove that O(1/ε^(2n)) copies are both necessary and sufficient if we restrict to tomography of pure states. Second, we establish that Gaussian states can be efficiently learned, a result that has been previously assumed but never rigorously proved. To do that, we answer the following fundamental question for Gaussian quantum information: If we approximate the first moment and covariance matrix of an unknown Gaussian state with precision ε, what is the resulting trace distance error on the state? Third, we show how to efficiently learn states prepared by Gaussian unitaries and a few local non-Gaussian evolutions, unveiling more on the structure of these slightly non-Gaussian systems.},
keywords = {Quantum information theory},
pubstate = {published},
tppubtype = {Talk}
}
While quantum state tomography has been extensively analysed for qubit and qudit systems, rigorous performance guarantees in terms of ε-approximation in trace distance remain largely unexplored for continuous variable quantum systems, due to subtleties that arise in the infinite-dimensional context. This work addresses this gap. First, we discover that to learn energy-constrained n-mode states, the sample complexity must scale with ε as Ω(1/ε^(2n)). This is in sharp contrast with the n-qubit case, where the ε-scaling is O(1/ε^2) — thereby establishing the extreme inefficiency of continuous variable tomography. Remarkably, we prove that O(1/ε^(2n)) copies are both necessary and sufficient if we restrict to tomography of pure states. Second, we establish that Gaussian states can be efficiently learned, a result that has been previously assumed but never rigorously proved. To do that, we answer the following fundamental question for Gaussian quantum information: If we approximate the first moment and covariance matrix of an unknown Gaussian state with precision ε, what is the resulting trace distance error on the state? Third, we show how to efficiently learn states prepared by Gaussian unitaries and a few local non-Gaussian evolutions, unveiling more on the structure of these slightly non-Gaussian systems.
18.
Chengkai Zhu, Yin Mo, Yu-Ao Chen, Xin Wang
Reversing Unknown Quantum Processes via Virtual Combs: for Channels with Limited Information Talk
2024.
Abstract | Tags: Quantum algorithms, Quantum information theory
@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}
}
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.
19.
Robert Salzmann, Bjarne Bergh, Nilanjana Datta
Robustness of Fixed Points of Quantum Channels and Application to Approximate Quantum Markov Chains Talk
2024.
Abstract | Tags: Quantum information theory
@Talk{T24_228,
title = {Robustness of Fixed Points of Quantum Channels and Application to Approximate Quantum Markov Chains},
author = {Robert Salzmann and Bjarne Bergh and Nilanjana Datta},
year = {2024},
date = {2024-01-01},
abstract = {We address the following question: Given a quantum channel and a quantum state which is almost a fixed point of the channel, can we find a new channel and a new state, which are respectively close to the original ones, such that they satisfy an exact fixed point equation? This question can be asked under many interesting constraints in which the original channel and state are assumed to have certain structures which the new channel and state are supposed to satisfy as well. We answer this question in the affirmative under fairly general assumptions on aforementioned structures through a compactness argument. We then concentrate on specific structures of states and channels and establish explicit bounds on the approximation errors between the original- and new states and channels respectively. We find a particularly desirable form of these approximation errors for a variety of interesting examples, including the structure of general quantum states and general quantum channels, unitary channels and unital channels. On the other hand, for the setup of bipartite quantum systems for which the considered channels are demanded to act locally, we are able to lower bound the possible approximation errors. Here, we show that these approximation errors necessarily scale in terms of the dimension of the quantum system in an undesirable manner. We apply our results to the robustness question of quantum Markov chains (QMC) and establish the following: For a tripartite quantum state we show the existence of a dimension-dependent upper bound on the distance to the set of QMCs, which decays as the conditional mutual information of the state vanishes.},
keywords = {Quantum information theory},
pubstate = {published},
tppubtype = {Talk}
}
We address the following question: Given a quantum channel and a quantum state which is almost a fixed point of the channel, can we find a new channel and a new state, which are respectively close to the original ones, such that they satisfy an exact fixed point equation? This question can be asked under many interesting constraints in which the original channel and state are assumed to have certain structures which the new channel and state are supposed to satisfy as well. We answer this question in the affirmative under fairly general assumptions on aforementioned structures through a compactness argument. We then concentrate on specific structures of states and channels and establish explicit bounds on the approximation errors between the original- and new states and channels respectively. We find a particularly desirable form of these approximation errors for a variety of interesting examples, including the structure of general quantum states and general quantum channels, unitary channels and unital channels. On the other hand, for the setup of bipartite quantum systems for which the considered channels are demanded to act locally, we are able to lower bound the possible approximation errors. Here, we show that these approximation errors necessarily scale in terms of the dimension of the quantum system in an undesirable manner. We apply our results to the robustness question of quantum Markov chains (QMC) and establish the following: For a tripartite quantum state we show the existence of a dimension-dependent upper bound on the distance to the set of QMCs, which decays as the conditional mutual information of the state vanishes.
20.
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.
21.
Bo Yang, Elham Kashefi, Dominik Leichtle, Harold Ollivier
State Purification with Symmetry Subgroup Projectors Talk
2024.
Abstract | Tags: Quantum algorithms, Quantum information theory
@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}
}
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.
22.
Niklas Galke, Lauritz Luijk, Henrik Wilming
Sufficiency of Rényi divergences Talk
2024.
Abstract | Tags: Quantum communication, Quantum information theory
@Talk{T24_343,
title = {Sufficiency of Rényi divergences},
author = {Niklas Galke and Lauritz Luijk and Henrik Wilming},
year = {2024},
date = {2024-01-01},
abstract = {A set of classical or quantum states is equivalent to another one if there exists a pair of classical or quantum channels mapping either set to the other one. For dichotomies (pairs of states), this is closely connected to (classical or quantum) Rényi divergences (RD) and the data-processing inequality: If a RD remains unchanged when a channel is applied to the dichotomy, then there is a recovery channel mapping the image back to the initial dichotomy. Here, we prove for classical dichotomies that equality of the RDs alone is already sufficient for the existence of a channel in any of the two directions and discuss some applications. In the quantum case, all families of quantum RDs are seen to be insufficient because they cannot detect anti-unitary transformations. Thus, including anti-unitaries, we pose the problem of finding a sufficient family. It is shown that the Petz and maximal quantum RD are still insufficient in this more general sense and we provide evidence for sufficiency of the minimal quantum RD. As a side result of our techniques, we obtain an infinite list of inequalities fulfilled by the classical, the Petz quantum, and the maximal quantum RDs. These inequalities are not true for the minimal quantum RDs. Our results further imply that any sufficient set of conditions for state transitions in the resource theory of athermality must be able to detect time-reversal.},
keywords = {Quantum communication, Quantum information theory},
pubstate = {published},
tppubtype = {Talk}
}
A set of classical or quantum states is equivalent to another one if there exists a pair of classical or quantum channels mapping either set to the other one. For dichotomies (pairs of states), this is closely connected to (classical or quantum) Rényi divergences (RD) and the data-processing inequality: If a RD remains unchanged when a channel is applied to the dichotomy, then there is a recovery channel mapping the image back to the initial dichotomy. Here, we prove for classical dichotomies that equality of the RDs alone is already sufficient for the existence of a channel in any of the two directions and discuss some applications. In the quantum case, all families of quantum RDs are seen to be insufficient because they cannot detect anti-unitary transformations. Thus, including anti-unitaries, we pose the problem of finding a sufficient family. It is shown that the Petz and maximal quantum RD are still insufficient in this more general sense and we provide evidence for sufficiency of the minimal quantum RD. As a side result of our techniques, we obtain an infinite list of inequalities fulfilled by the classical, the Petz quantum, and the maximal quantum RDs. These inequalities are not true for the minimal quantum RDs. Our results further imply that any sufficient set of conditions for state transitions in the resource theory of athermality must be able to detect time-reversal.
23.
André Chailloux, Jean-Pierre Tillich
The Quantum Decoding Problem Talk
2024.
Abstract | Tags: Proceedings, Quantum algorithms, Quantum information theory
@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}
}
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.
24.
Yixian Qiu, Kelvin Koor, Patrick Rebentrost
The Quantum Esscher Transform Talk
2024.
Abstract | Tags: Quantum algorithms, Quantum information theory
@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}
}
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.
