Hi all,
Tomorrow our visitor Michèle Wigger will tell us about "Strong and $\epsilon$-Dependent Converses for Classical Coding and Hypothesis Testing Problems". See below for the abstract. The talk will take place at 2pm in HIT E 41.1 or on Zoom: https://ethz.zoom.us/j/362994444.
Best,
Ladina
%%%%%%%%%%%
Title: "Strong and $\epsilon$-Dependent Converses for Classical Coding and Hypothesis Testing Problems"
Abstract:
This is a classical talk, where I will be presenting new simple strong converse proofs for basic classical source coding and hypothesis testing problems, and if time permits also for classical channel coding. For the basic source and channel coding setups, the proofs only use a change of measure argument on the strongly typical set and the asymptotic analysis of the new measure. This proof method is also extended to a source coding setup under relaxed expected rate constraints, in which case the minimum compression rate depends on the allowed probability of error $\epsilon$ and an $\epsilon$-dependent converse is required. In the second part of the talk we present converse proof methods for hypothesis testing setups, where the change of measure argument is not sufficient, but has to be completed with proofs of asymptotic Markov Chains. We again also consider expected resource or secrecy constraints and provide probability-of-error-dependent converse proofs under these expected constraints.
Hi all,
Tomorrow we will have two talks:
Eliott Mamon will tell us about 'How to model quantum bomb-testing? A framework for “interaction-free” experiments'.
Alexander Schmidhuber will talk about 'Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis'.
See below for the abstracts. The talks will take place at 2pm in HIT E 41.1 or on Zoom: https://ethz.zoom.us/j/362994444.
Best,
Ladina
%%%%%%
Title:
How to model quantum bomb-testing? A framework for “interaction-free” experiments
Abstract:
Taking inspiration from the "counterfactual computation" framework of [1], an axiomatic framework for studying quantum experiments that can lead to counterfactual outcomes, and more generally, interaction-free outcomes, is proposed. It is based on a separation of the Hilbert space into "off" and "on" subspaces. To both motivate the framework itself and better understand what devices one should actually choose in it to model a given experimental setup, we start by introducing a purely classical "interaction-free" framework (in which counterfactual outcomes are impossible by construction). There, one makes a conceptually simpler ansatz of such a classical framework instance, and then, applies a quantum extension scheme, wherein several "choices of coherence" are left to be made --- first within off-states and on-states, and then between the two. We highlight a resulting feature of the framework: if a lack of coherence between off-states and on-states is chosen in the extension scheme for a particular device, then the resulting quantum setup cannot yield counterfactual outcomes for the other devices.
We apply our framework to approach modeling quantum "bomb-testing" experiments, illustrating how the framework structures the different candidate models together. We also discuss how the framework deals with modeling "quantum Zeno effect" type bomb-testing protocols like the Kwiat et al. protocol of [2]. Notably, we underline how the usual notion of "interaction-free" on them is recovered within our framework.
Lastly, we consider formalizing an "existence of noncontextual model" question for a given protocol of our framework. We then numerically, using the unit separability criterion of [3], assess this question in the negative for the Kwiat et al. N insertion protocol, for N = 4,...,8.
[1] Graeme Mitchison and Richard Jozsa. "Counterfactual computation". Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences 457.2009 (2001), pp. 1175–1193.
[2] Paul Kwiat et al. “Interaction-free measurement”. Physical Review Letters 74.24(1995), pp. 4763–4766.
[3] Victor Gitton and Mischa P. Woods. "Solvable criterion for the contextuality of any prepare-and-measure scenario". Quantum 6 (2022), p. 732.
Title:
Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis (https://arxiv.org/abs/2209.14286)
Abstract:
Quantum algorithms for topological data analysis (TDA) have received a surge of attention recently. They seem to provide an exponential advantage over the best classical approach while remaining immune to dequantization procedures and the data-loading problem. In this talk, I will argue that quantum algorithms for TDA run in exponential time for almost all inputs by showing that the central problem of TDA - estimating Betti numbers - is intractable even for quantum computers. Specifically, we prove that the problem of computing Betti numbers exactly is #P-hard, while the problem of approximating Betti numbers up to multiplicative error is NP-hard. Because quantum computers are not expected to solve #P-hard or NP-hard problems in sub-exponential time, our results imply that quantum algorithms for TDA only provide a polynomial advantage. We verify our claim by showing that the seminal quantum algorithm for TDA developed by Lloyd et al. achieves a quadratic speedup over the best classical approach in almost all cases. Finally, we argue that an exponential quantum advantage can be recovered if problems beyond TDA are considered.
Hi all,
This week, we will have two talks on Tuesday and one talk on Wednesday.
On Tuesday Simon Cichy will tell us about 'A perturbative gadget for delaying the onset of barren plateaus in variational quantum algorithms' and Marcus Haberland will talk about 'Security of Relativistic Quantum Key Distribution'. These talks will take place at 2pm in HIT E 41.1 or on Zoom https://ethz.zoom.us/j/362994444.
On Wednesday Paul Colomer Saus will tell us about 'Quantum-enhanced estimation of a mode parameter’. This talk will take place at 2pm in HIT H51 or on Zoom https://ethz.zoom.us/j/362994444.
See below for the abstracts.
Best,
Ladina
%%%%%%
Title: A perturbative gadget for delaying the onset of barren plateaus in variational quantum algorithms (https://arxiv.org/abs/2210.03099)
Abstract:
Variational quantum algorithms are being explored as a promising approach to finding useful applications for noisy intermediate-scale quantum computers. However, cost functions corresponding to many problems of interest are inherently global, defined by Hamiltonians with many-body interactions. Consequently, the optimization landscape can exhibit exponentially vanishing gradients, so-called barren plateaus, rendering optimal solutions difficult to find. Strategies for mitigating barren plateaus are therefore needed to make variational quantum algorithms trainable and capable of running on larger-scale quantum devices. In this work, we contribute the toolbox of perturbative gadgets to the portfolio of methods being explored in the quest for making noisy intermediate-scale quantum devices useful. Specifically, we introduce a novel perturbative gadget, tailored to variational quantum algorithms, that can be used to avoid barren plateaus. Our perturbative gadget encodes an arbitrary many-body Hamiltonian corresponding to a global cost function into the low-energy subspace of a three-body Hamiltonian. Our construction requires rk additional qubits for a k-body Hamiltonian comprising r terms. We provide rigorous guarantees on the optimization of the local cost function defined by our three-body gadget Hamiltonian with respect to the original cost function, and we prove that this local cost function exhibits non-vanishing gradients, thus delaying the onset of barren plateaus. We then provide numerical demonstrations to show the functioning of our approach.
%%%%%%
Title: Security of Relativistic Quantum Key Distribution
Abstract:
In this Master’s Thesis, we prove security for Relativistic Quantum Key Distribution (QKD) by utilizing the fact that any malicious adversary is constrained to respect causality. This can be achieved easily in experiments by granting Alice and Bob access to synchronized clocks in addition to their quantum machines, as they can then time the different steps of their QKD protocol appropriately.
We design three novel QKD protocols, which are based on ideas from [KRKM18]. We utilize the Generalized Entropy Accumulation Theorem from [MR22] to numerically prove finite-size security against general adversarial attacks and compute the key rates for two of them. We explain our reasoning as to why we conjecture the third photonic implementation to be secure as well, based on the idea of squashing from [GBN+14]. We show that by relying solely on causality as a security guarantee in QKD, one can establish high key rates and may achieve the maximum theoretically allowed scaling of the key rate in losses. This has importance for satellite-based and large-scale QKD networks and proves that entropic uncertainty, which grants security for well-established protocols like B92 and BB84, is not the only concept that can be used to prove QKD secure.
Literature:
[KRKM18] - K. S. Kravtsov, I. V. Radchenko, S. P. Kulik, and S. N. Molotkov. Relativistic quantum key distribution system with one-way quantum communication. Sci Rep, 8(6102), Apr 2018. doi:10.1038/s41598- 018-24533-6.
[MR22] - Tony Metger and Renato Renner. Security of quantum key distribution from generalised entropy accumulation, 2022. doi:10.48550/ARXIV.2203.04993.
[GBN+14] - O. Gittsovich, N. J. Beaudry, V. Narasimhachar, R. Romero Alvarez, T. Moroder, and N. Lütkenhaus. Squashing model for detectors and applications to quantum-key-distribution protocols. Phys. Rev. A, 89:012325, Jan 2014. doi:10.1103/PhysRevA.89.012325.
%%%%%
Title: Quantum-enhanced estimation of a mode parameter.
Abstract:
High-precision experiments in interferometry, spectroscopy, positioning, and timing use light parameters to encode information. Therefore, it is critical to estimate them accurately. Using non-classical states of light, it is possible to enhance the sensitivity on the estimation of light-mode parameters (such as the wavelength or the spatial shape) beyond the standard quantum limit. In the presentation, we will discuss how to estimate with quantum-enhanced sensitivity a radial displacement of a light beam in an arbitrary direction and the wavelength. We will find which light-mode schemes allow quantum-enhanced sensitivities, and which quantum states maximize them.
Hi all,
Tomorrow Gerard Aguilar Tapia will tell us about his master thesis entitled 'Error mitigation for near-term quantum computers using Lanczos subspace expansion'. See below for the abstract. The talk will take place at 2pm in HIT E 41.1 or on Zoom: https://ethz.zoom.us/j/362994444.
Best,
Ladina
%%%%%%%%
Among the numerous approaches that have been proposed for error mitigation in the recent years, the Lanczos subspace expansion stands as an interesting candidate for the task. In this talk I present my thesis work, for which I performed a detailed study of this method for mitigating noise in electronic structure calculations. It will be shown that unlike other schemes it is capable of exponentially supressing both coherent and incoherent noise just at the cost of some additional Pauli measurements. On the other hand, I formally assess some of the downsides of the algorithm that hinder its utility in real scenarios, namely: the unfavourable scaling of the number of measurements and the instability against shot-noise. With that I will also mention some of the attempts to overcome this issues.
Hi all,
Tomorrow Maarten Grothus will tell us about his master thesis with Vilasini entitled 'Compatibility of Cyclic Causal Structures with Spacetime in General Theories with Free Interventions'. See below for the abstract. The talk will take place at 2pm in HIT E 41.1 or on Zoom: https://ethz.zoom.us/j/362994444.
Best,
Ladina
%%%%%
By relating and ordering events, causality constitutes a pivotal feature of our world.
However, different notions of causality exist, whose relation is not completely under-
stood so far. In particular, we may consider both information-theoretic causality,
covering the operational idea of information processing, and relativistic causality,
linked to a light cone structure limiting signalling to the future. In this work, we
improve on various results on the connection between both notions, as studied by
V. Vilasini and R. Colbeck in [1][2], in particular for questions of cyclicity.
In the first part, we take an information-theoretic point of view, reviewing general,
potentially cyclic or fine-tuned causal models. Here, the most general way of sig-
nalling is given by a concept of generalized affects relations, which use interventions
on the model to uncover relations between nodes in these graphs. Building from
their results, we study the properties of these affects relations and establish new
ways to use them to characterize causal structures. focusing on higher-order (HO)
affects relations in particular, we can use knowledge of the absence of affects re-
lations for causal inference. Further, we demonstrate a complete and constructive
way to detect causal loops from a set of affects relations.
In the second part, we embed these causal structures into a generic spacetime whose
causal structure forms a partial order. Here, it was shown in [2] that limiting sig-
nalling to the relativistic future does not suffice to generally rule out operationally
detectable causal loops. In light of this, we propose additional stability conditions
on the spacetime embedding and find that this can rule out a class of operationally
detectable loops that cannot be ruled out by the principle of no-signalling (out-
side the relativistic future) alone. We then propose a number of order-theoretic
properties that we conjecture to hold in Minkowski spacetime with d ≥ 2 spatial
dimensions. This would imply that in contrast to our result for generic spacetimes,
in that Minkowski case, the no-signalling principle is indeed sufficient for ruling
out this class of loops. Finally, we deduce novel restrictions for compatibility for
certain HO affects relations.
[1] Phys. Rev. A, 106, p. 032204 (2022)
[2] Phys. Rev. Lett., 129, p. 110401 (2022)