Third Kyoto Workshop on Quantum Information, Computation, and Foundations

Organized by the Quantum Information Unit at the Yukawa Institute for Theoretical Physics, Kyoto University

To be held online from October 17 to 21, 2022


The third workshop on Quantum Information, Computation, and Foundations 2022 (QICF22) will focus on device independent quantum information processing, quantum resource theories, quantum statistical comparison, quantum combs, quantum designs, the geometry of the state space, foundations of quantum theory, quantum communication, quantum computing, quantum computational complexity, quantum cryptography, and other related topics.

Previous Instances

Second Kyoto Workshop on Quantum Information, Computation, and Foundation (QICF21)

First Kyoto Workshop on Quantum Information, Computation, and Foundation (QICF20)


Please register through our registration form. Registration is free.

Invited Speakers

Name Affiliation Title of the talk
Antonio Acin ICFO Barcelona, Spain Network quantum information processing
Prabhanjan Ananth UCSB, USA Pseudorandom quantum states, revisited: Improved analysis, new definitions, constructions and cryptographic applications
Alessandro Bisio University of Pavia, Italy Causal and compositional structure of higher order quantum maps
Zvika Brakerski Weizmann Institute of Science "Cryptology = cosmology" in black-hole radiation decoding
Francesco Buscemi Nagoya University, Japan Observational entropy, coarse-grainings, and Petz recovery
Shujiao Cao Chinese Academy of Sciences On constructing one-way quantum state generators
Giulio Chiribella University of Hong Kong Asymptotically optimal programming of unitary gates
Michele Dall'Arno Kyoto University, Japan Minimally-committal quantum measurements
Nilanjana Datta University of Cambridge, UK Fully undistillable quantum states are separable
Peter Frenkel Lorand Eotvos University, Hungary An integral formula for quantum relative entropy
Ryu Hayakawa Kyoto University, Japan Improved hardness results for the guided local hamiltonian problem
Anna Jencova Slovak Academy of Sciences, Slovakia On characterizations of quantum incompatibility and steering
Qipeng Liu Simons Institute for the Theory of Computing, USA Non-uniformity and quantum advice in the random oracle model
Alex Lombardi MIT, USA Interactive quantum advantage from any non-local game
Mio Murao University of Tokyo, Japan Fully-quantum learning: Comparison of unknown unitary channels with multiple uses
Paolo Perinotti University of Pavia, Italy On the Heisenberg thought experiment and notions of compatibility
Luowen Qian Boston University, USA On the computational hardness needed for quantum cryptography
Bartosz Regula University of Tokyo, Japan Projective divergences and limitations of probabilistic state transformations
Simone Roncallo University of Pavia, Italy Noise deconvolution on multi-qubit systems: noiseless results from noisy measurements
Robert Salzmann University of Cambridge, UK Total insecurity of communication via strong converse for quantum privacy amplification
Michal Sedlak Slovak Academy of Sciences, Slovakia Incompatibility of quantum instruments
Paul Skrzypczyk University of Bristol, UK Quantum betting tasks
Ryuji Takagi Nanyang Technological University, Singapore Correlation in catalysts enables arbitrary manipulation of quantum coherence
Mihaly Weiner Budapest University of Technology and Economics, Hungary Quantum hypothesis testing: a conjecture disproved
Takashi Yamakawa NTT, Japan Verifiable quantum advantage without structure
Jun Yan Jinan University, China Computational quantum bit commitment and its role in quantum cryptography
Lin Htoo Zaw National University of Singapore Detecting quantumness and entanglement with precessions
Jiayu Zhang Caltech, USA Classical verification of quantum computations in linear time
Karol Zyczkowski Jagiellonian University, Poland Monge distances between quantum states


Japan time Monday 17/10 Tuesday 18/10 Wednesday 19/10 Thursday 20/10 Friday 21/10
10:00 - 11:00 Lombardi Qian Yan Hayakawa Cao
11:00 - 12:00 Ananth Liu Zhang Yamakawa
15:15 - 16:00 Regula Zaw Brakerski Weiner
16:00 - 16:45 Murao Buscemi Chiribella Dall’Arno
16:45 - 17:30 Zyczkowski Bisio Perinotti Takagi Jencova
17:30 - 18:15 Datta Sedlak Roncallo Salzmann
18:15 - 19:00 Frenkel Skrzypczyk Acin


Michele Dall'Arno, Andres F. Ducuara, and Tomoyuki Morimae. Please feel free to contact us for any inquiry about the workshop.


Observational entropy, coarse-grained states, and irretrodictability

Francesco Buscemi, Nagoya University, Japan

Besides the quantity that is nowadays eponymously known as the von Neumann entropy, in his 1932 book von Neumann discusses also another entropic quantity, which he calls "macroscopic", arguing that it is the latter, and not the former, the relevant quantity to use when analyzing thermodynamic systems. However, for a long time, von Neumann's "other" entropy was largely forgotten and has appeared only sporadically in the literature, overshadowed by its more famous sibling. In this talk I will discuss a recent generalization of von Neumann's macroscopic entropy, called "observational entropy", focusing on its mathematical properties (leading to a strong version of Petz recovery) and statistical interpretation. Concerning the latter in particular, I will argue that observational entropy perfectly fits within Jeffrey's theory of probability kinematics and provides the embodiment of Watanabe's "irreversibility is irretrodictability" maxim. The content of this talk is based on discussions and joint works with Clive Aw and Valerio Scarani (NUS, Singapore), Dominik Safranek (IBS, Korea), and Joseph Schindler (UAB, Spain).

An integral formula for quantum relative entropy

Peter Frenkel, Lorand Eotvos University, Hungary

A new, maybe unexpected integral representation of quantum relative entropy can be used to give a simple proof of the monotonicity of quantum relative entropy under trace-preserving positive linear maps -- complete positivity of the map need not be assumed. This data-processing inequality was first established by Müller-Hermes and Reeb, building on the work of Beigi.

Quantum betting tasks

Paul Skrzypczyk, University of Bristol, UK

In this talk I will present recent work (carried out in collaboration with Andres Ducuara), on betting in the context of quantum information. In particular, we propose a generalisation of quantum discrimination and exclusion tasks, which we call quantum betting tasks, where a gambler places bets. Crucially, we take into account the risk tendency of the gambler, by using concepts from expected utility theory. I will show that in this setting, the usefulness of side-information to a risk-averse gambler is exactly captured by an information-theoretic quantity based upon Renyi entropies (which can be viewed as a Renyi generalisation of the mutual information). Reference: PRX Quantum 3, 020366 (2022).

Monge distances between quantum states

Karol Zyczkowski, Jagiellonian University, Poland

Processing quantum information one often needs to distinguish between two given quantum states or to describe how close they are apart. Depending on a particular application various distances are used. While the standard solutions (including trace, Hilbert-Schmidt or fidelity-based Bures distance) are unitarily invariant, for some purposes it is convenient to work with more general notions. To measure the distance between any two quantum states one can consider the Monge distance between the corresponding Husimi distributions (Q-functions). This approach works for pure and mixed states for finite and infinite Hilbert spaces [1]. As the Monge problem is solved with respect to the underlying classical distance the following semiclassical property holds: the distance between any two coherent quantum states is equal to the Euclidean distance between the corresponding points in the classical phase space. Hence this distance is not unitarily invariant and can be applied to analyze a quantum analogue of the Lyapunov exponent. In the case of infinite dimensional Hilbert space one applies the standard harmonic oscillator coherent states, while for a $N$--dimensional space we rely on $SU(2)$ spin--coherent states. For several families of states it is possible to evaluate such a distance analytically. In the case of a finite $N$ each pure state can be described in the stellar representation by a constellation of $k=N-1$ Majorana stars -- the zeros of the corresponding Husimi function. The simplified Monge distance can be then computed by solving a simpler, discrete Monge problem for two $k$-point probability distributions. An alternative approach of Kantorovich and Wasserstein provides an explicit symmetry between both quantum states analyzed. Furthermore, such a definition does not depend on the selection of the set of coherent states. However, it depends on the choice of the cost matrix, while the optimization is performed over all coupling matrices representing quantum states in $N^2$--dimensional space with fixed partial traces [2]. Literature [1] K. Zyczkowski and W.Slomczynski, "Monge distance between quantum states", J.Phys. A 31, 9095 (1998). [2] S. Friedland, M. Eckstein, S. Cole, K. Zyczkowski, Quantum Monge-Kantorovich problem and transport distance between density matrices, Phys. Rev. Lett. 129, 110402 (2022).

Computational quantum bit commitment and its role in quantum cryptography

Jun Yan, Jinan University, China

While unconditionally-secure quantum bit commitment (allowing both quantum computation and communication) is impossible, researchers turn to study the complexity-based one, a.k.a. computational quantum bit commitment. A (computational) canonical (non-interactive) quantum bit commitment scheme refers to a kind of scheme such that the commitment consists of just a single (quantum) message from the sender to the receiver that later can be opened by uncomputing the commit stage. In this work, we study general properties of computational quantum bit commitments through the lens of canonical quantum bit commitments. Among other results, we in particular obtain the following two: 1. Any computational quantum bit commitment scheme can be converted into the canonical (non-interactive) form (with its sum-binding property preserved). 2. Two flavors of canonical quantum bit commitments are equivalent; that is, canonical computationally-hiding statistically-binding quantum bit commitment exists if and only if the canonical statistically-hiding computationally-binding one exists. Combining this result with the first one, it immediately implies (unconditionally) that computational quantum bit commitment is symmetric. Canonical quantum bit commitments can be based on quantum-secure one-way functions or pseudorandom quantum states. But in our opinion, the formulation of canonical quantum bit commitment is so clean and simple that itself can be viewed as a plausible complexity assumption as well. We propose to explore canonical quantum bit commitment from perspectives of both quantum cryptography and quantum complexity theory in the future.

On the computational hardness needed for quantum cryptography

Luowen Qian, Boston University, USA

In the classical model of computation, it is well established that one-way functions (OWF) are essential for almost every computational cryptographic application. In the quantum setting, however, OWFs appear not to be essential (Kretschmer 2021; Ananth et al., Morimae and Yamakawa 2022), and the question of whether a minimal primitive exists remains open. We consider EFI pairs — efficiently samplable, statistically far but computationally indistinguishable pairs of distributions. Building on the work of Yan (2022) which shows equivalence between EFI pairs and statistical commitment schemes, we show that EFI pairs are necessary and sufficient for a large class of quantum-cryptographic applications. Specifically, while it was known how to construct commitments schemes, oblivious transfer, and general secure multiparty computation from any EFI, we show how to construct EFI pairs from minimalistic versions of each one of these primitives. We also construct from EFI quantum computational zero knowledge (𝖰𝖢𝖹𝖪) proofs for all of 𝖰𝖨𝖯, and construct EFI pairs from essentially any non-trivial 𝖰𝖢𝖹𝖪. This suggests that, for much of quantum cryptography, EFI pairs play a similar role to that played by OWFs in the classical setting: they are simple to describe, essential, and also serve as a linchpin for demonstrating equivalence between primitives. Based on joint work with Zvika Brakerski and Ran Canetti.

Detecting quantumness and entanglement with precessions

Lin Htoo Zaw, National University of Singapore

We recently introduced a family of protocols that detect the nonclassicality of suitable states of a single quantum system, under the sole assumption that the measured dynamical observable undergoes a uniform precession [1]. This was based on an unexpected observation by Tsirelson about the quantum harmonic oscillator: despite its time evolution being the same as its classical counterpart—a precession in phase space—its nonclassicality can be detected by probing its position at different times [2]. After covering the protocol for both the harmonic oscillator (uniform precession in phase space) and finite- dimensional spins (uniform precession in real space), I will present some recent results about witnessing entanglement of two harmonic oscillators, and the extension of the protocol to systems with anharmonic dynamics. [1] Zaw, L. H., Aw, C. C., Lasmar, Z., & Scarani, V. (2022). Detecting quantumness in uniform precessions. arXiv:2204.10498. [2] Tsirelson, B. (2006). How often is the coordinate of a harmonic oscillator positive?. arXiv:quant-ph/0611147.

Classical verification of quantum computations in linear time

Jiayu Zhang, Caltech, USA

In the quantum computation verification problem, a quantum server wants to convince a client that the output of evaluating a quantum circuit C is some result that it claims. This problem is considered very important both theoretically and practically in quantum computation [arXiv:1709.06984], [arXiv:1704.04487], [arXiv:1209.0449]. The client is considered to be limited in computational power, and one desirable property is that the client can be completely classical, which leads to the classical verification of quantum computation (CVQC) problem. In terms of the total time complexity, the fastest single-server CVQC protocol so far has complexity O(poly(κ)|C|3) where |C| is the size of the circuit to be verified and κ is the security parameter, given by Mahadev [arXiv:1804.01082]. In this work, by developing new techniques, we give a new CVQC protocol with complexity O(poly(κ)|C|), which is significantly faster than existing protocols. Our protocol is secure in the quantum random oracle model [arXiv:1008.0931] assuming the existence of noisy trapdoor claw-free functions [arXiv:1804.00640], which are both extensively used assumptions in quantum cryptography. Our protocol allows for parallel verifiable preparation of Lindependently random states in this form (up to a constant overall error and a possibly unbounded server-side simulator), and runs in only O(poly(κ)L) time and constant rounds; for comparison, existing works (even for possibly simpler state families) all require very large or unestimated time and round complexities [arXiv:1904.06320][arXiv:1904.06303][arXiv:2201.13445][arXiv:2201.13430].

Incompatibility of quantum instruments

Michal Sedlak, Slovak Academy of Sciences, Slovakia

Quantum instruments describe outcome probability as well as state change induced by measurement of a quantum system. Incompatibility of two instruments, i. e. the impossibility to realize them simultaneously on a given quantum system, generalizes incompatibility of channels and incompatibility of positive operator-valued measures (POVMs). We derive implications of instrument compatibility for the induced POVMs and channels. We also study relation of instrument compatibility to the concept of non-disturbance. Finally, we prove equivalence between instrument compatibility and post-processing of certain instruments, which we term complementary instruments. We illustrate our findings on examples of various classes of instruments.

Improved hardness results for the guided local hamiltonian problem

Ryu Hayakawa, Kyoto University, Japan

Estimating the ground state energy of a local Hamiltonian is a central problem in quantum chemistry. In order to further investigate its complexity and the potential of quantum algorithms for quantum chemistry, Gharibian and Le Gall (STOC 2022) recently introduced the guided local Hamiltonian problem (GLH), which is a variant of the local Hamiltonian problem where an approximation of a ground state is given as an additional input. In this talk, we optimally improve both the locality and the overlap parameters of the previous result: we show that this quantum advantage (BQP-completeness) persists even with 2-local Hamiltonians, and even when the guiding state has overlap (inverse-polynomially) close to 1 with a ground state. Moreover, we show that the BQP-completeness also holds for 2-local physically motivated Hamiltonians on a 2D square lattice or a 2D triangular lattice such as the (antiferromagnetic) Heisenberg model or the (antiferromangetic) XY model. This makes a further step towards establishing practical quantum advantage in quantum chemistry. This is a joint work with Sevag Gharibian, François Le Gall, and Tomoyuki Morimae. [Reference:arXiv:2207.10250]

Correlation in catalysts enables arbitrary manipulation of quantum coherence

Ryuji Takagi, Nanyang Technological University, Singapore

Quantum resource manipulation may include an ancillary state called a catalyst, which aids the transformation while restoring its original form at the end. Here, we show that allowing correlation among multiple catalysts can offer arbitrary power in the manipulation of quantum coherence. We prove that any state transformation can be accomplished with an arbitrarily small error by covariant operations with catalysts that may create a correlation within them while keeping their marginal states intact. This presents a new type of embezzlement-like phenomenon, in which the resource embezzlement is attributed to the correlation generated among multiple catalysts. We extend our analysis to general resource theories and characterize achievable transformations in relation to their asymptotic state transformations. Our results provide a step toward the complete characterization of the resource transformability in quantum thermodynamics with correlated catalysts. Reference: Phys. Rev. Lett. 128, 240501 (2022)

Projective divergences and limitations of probabilistic state transformations

Bartosz Regula, University of Tokyo, Japan

We show how a quantum divergence based on the Hilbert projective metric finds use in understanding the transformations of quantum states under some restrictions on the allowed operations. In very general classes of quantum resource theories, we prove that probabilistic convertibility between quantum states is completely determined by this single monotone. We analogously find that the asymptotic rates of transformations of quantum states under probabilistic protocols are given precisely by a regularisation of the projective divergence. The results apply to many relevant cases such as transformations of quantum dichotomies and entanglement distillation under non-entangling operations. Based on arXiv:2109.04481 and arXiv:2209.03362.

Non-uniformity and quantum advice in the random oracle model

Qipeng Liu, Simons Institute for the Theory of Computing, USA

QROM (quantum random oracle model), introduced by Boneh et al. (Asiacrypt 2011), captures all generic algorithms but fails to describe non-uniform quantum algorithms with preprocessing power, which receives a piece of bounded classical or quantum advice. In this talk, we will show that even quantum advice is almost as good/bad as classical advice for many natural security games in the QROM, improved the bounds by Chung et al. (FOCS 2020). Finally, we show that for some contrived games in the QROM, quantum advice can be exponentially better than classical advice for specific parameter regimes.

Fully-quantum learning: Comparison of unknown unitary channels with multiple uses

Mio Murao, University of Tokyo, Japan

Efficiently learning properties of unknown quantum objects is a fundamental task in quantum mechanics and quantum information. When there are two unknown quantum objects, and if we want to learn just the relationship between the objects, a method to directly compare the two objects without identifying their descriptions is preferable, especially when the number of available copies of each target object is limited. Comparison of quantum objects is a task to determine whether two unknown quantum objects are the same or different, and comparison of quantum states, quantum channels, and quantum measurements have been investigated. In general, repeated uses of quantum objects improve the success probability of comparison. The optimal strategy of pure-state comparison, the comparison of quantum states for the case of multiple copies of each unknown pure state, is known, but the optimal strategy of unitary comparison, the comparison of quantum channels for the case of multiple uses of each unknown unitary channel, was not known due to the complication of the varieties of causal order structures among the uses of each unitary channel. In this work, we investigate unitary comparison with multiple uses of unitary channels based on the quantum tester formalism. We obtain the optimal minimum-error strategy and the optimal unambiguous strategy of unitary comparison of two unknown d-dimensional unitary channels when the number of uses of the channels satisfies a certain condition. These optimal strategies are implemented by parallel uses of the unitary channels, even though all sequential and adaptive strategies implementable by the quantum circuit model are considered. When the number of the smaller uses of the unitary channels is fixed, the optimal averaged success probability is achieved by a certain number of uses of the other channel. This feature contrasts with the case of pure-state comparison, where adding more copies of the unknown pure states always improves the optimal averaged success probability. It highlights the difference between corresponding tasks for states and channels, which has been previously shown for quantum discrimination tasks. Reference: Y. Hashimoto, A. Soeda and M. Murao, Comparison of unknown unitary channels with multiple uses, arXiv:2208.12519

Causal and compositional structure of higher order quantum maps

Alessandro Bisio, University of Pavia, Italy

Quantum processes with indefinite causal structure emerge when we wonder which are the most general evolutions, allowed by quantum theory, of a set of local systems which are not assumed to be in any particular causal order. These processes can be described within the framework of higher-order quantum theory which, starting from considering maps from quantum transformations to quantum transformations, recursively constructs a hierarchy of quantum maps of increasingly higher order. In this work, we develop a formalism for quantum computation with indefinite causal structures; namely we characterize the computational structure of higher order quantum maps. Taking an axiomatic approach, the rules of this computation are identified as the most general compositions of higher order maps which are compatible with the mathematical structure of quantum theory. We provide a mathematical characterization of the admissible composition for arbitrary higher order quantum maps. We prove that these rules, which have a computational and information-theoretic nature, are determined by the more physical notion of the signalling relations between the quantum systems of the higher order quantum maps. Joint work with Luca Apadula and Paolo Perinotti.

Network quantum information processing

Antonio Acin, ICFO Barcelona, Spain

Small quantum networks consisting of several nodes sharing entangled states are within reach with current and near-term technologies. They offer new possibilities for quantuminformation processing beyond what achievable in standard point-to-point configurations. In this talk, quantum networks are considered in the device-independent scenario where devices are seen as quantum back boxes processing classical information. We first show how the characterization of correlations in quantum networks is related to the study of causal networks. We then present several results illustrating the possibilities these networks offer in the foundations of quantum physics or for the development of quantum information technologies. In the first case, we show how real quantum theory can be falsified in a small network consisting of three observers in an entanglement swapping configuration. In the second, we discuss a scheme to self-test any pure entangled state.

Quantum hypothesis testing: a conjecture disproved

Mihaly Weiner, Budapest University of Technology and Economics, Hungary

Say we receive n independent samples of a system, all in the same state with the promise that this state belongs to one of two given sets (i.e. we have a given "null" and "alternative" hyoptheses). Our task is to make a decision between the null and alternative hpotheses. It is clear that with the right strategy, error probabilities can be made to exponentially decrease with the sample size n. However, in the quantum case not so much was known about the possible exponents (more precisely: exponent-pairs) that can be achieved. In the classical case, an exponent pair can be achieved if and only if it is achievable for any (individual) pair of null and alternative states. It was conjectured, that the same holds in the quantum case, too. However, in the article (joint with M. Mosonyi and Zs. Szilagyi) we prove that this is false. In my talk I will give you some background, explain how we constructed counter-examples and mention some further (unpublished) results about the landscape of achievable error exponents.

Fully undistillable quantum states are separable

Nilanjana Datta, University of Cambridge, UK

Assume that Alice, Bob and Eve share a tripartite state |ψ ABE>. We prove that if Alice cannot distill entanglement with either Bob or Eve using this state and local operations with any one of the following configurations for classical communication: (A→B,A↔E),(A↔B,A→E), and (A↔B,A↔E), then the same is also true for the other two configurations. Moreover, this happens precisely when the state is such that both its reductions ρAB and ρAE are separable, which is further equivalent to the reductions being PPT. This, in particular, implies that any NPT bipartite state is such that either the state itself or its complement is 2-way distillable. In proving these results, we first obtain an explicit lower bound on the 2-way distillable entanglement of low rank bipartite states. Furthermore, we show that even though not all low rank states are 1-way distillable, a randomly sampled low rank state will almost surely be 1-way distillable. This is joint work with Satvik Singh and is available on arXiv:2207.05193.

Noise deconvolution on multi-qubit systems: noiseless results from noisy measurements

Simone Roncallo, University of Pavia, Italy

Quantum systems are sensitive to noise, whose action can be represented by quantum channels. Channels modify the system state and, thus, the expectation value of observables. We present a noise deconvolution technique for obtaining noiseless expectation values of noisy observables at the output of multi-qubit quantum channels. The protocol applies to any noise model, for any number of qubits and also in presence of correlations. For a generic observable affected by Pauli noise, it provides a quadratic speed-up, always producing a rescaling of its Pauli basis components. Deconvolution can still be achieved while experimentally estimating the noise parameters, whenever these are unknown, bypassing resource-heavy techniques like quantum process tomography. Reference arXiv:2207.12386 [quant-ph] (joint work with L. Maccone and C. Macchiavello).

On constructing one-way quantum state generators

Shujiao Cao, Chinese Academy of Sciences

As a quantum analogue of one-way function, the notion of one-way quantum state generator (OWSG) is recently introduced by Morimae and Yamakawa (CRYPTO'22), which is proved to be implied by the pseudorandom state and can be used to devise a construction of one-time secure digital signature. In this talk, we will give two variants of OWSG, which are weak OWSG and distributionally OWSG, and show the equivalence among these three primitives. Then, we will construct the distributionally OWSG and quantum commitment from some hard-on-average problem of quantum statistical zero-knowledge (QSZK) that doesn't belong to QMA relative to a quantum oracle.

On characterizations of quantum incompatibility and steering

Anna Jencova, Slovak Academy of Sciences, Slovakia

Incompatibility of quantum measurements (POVMs) can be described in terms of the post-processing preorder: a set of POVMs is compatible if and only if it has a common upper bound. For finite outcome measurements, we show a relation of this preorder to the Choquet order on (discrete) probability measures on the set of quantum states. Using this result, we study linear and quadratic incompatibility witnesses and incompatibility degrees. In the dichotomic case, relations to tensor norms, 1-summing constants and matrix convex sets are discussed. The same arguments can be applied to assemblages and steering.

Asymptotically optimal programming of unitary gates

Giulio Chiribella, University of Hong Kong

A universal quantum processor is a device that can approximately implement any desired quantum gate on a given system. The specification of the desired gate is provided by a program, which in most implementations of quantum computing consists of classical data. From the foundational point of view, however, it is important to explore the more general scenario where the program is itself a quantum system. In the past two decades, a major open question has been to determine how the size of the smallest quantum program scales with the required accuracy in the implementation of the desired gate. Here we answer the question, by proving a bound on the size of the program and designing a concrete protocol that attains the bound in the asymptotic limit. As a byproduct, our results provide improved bounds on the estimation of arbitrary unitary gates, and on the implementation of quantum protocols subject to conservation laws.

Verifiable quantum advantage without structure

Takashi Yamakawa, NTT, Japan

We show the following hold, unconditionally unless otherwise stated, relative to a random oracle with probability 1: - There are NP search problems solvable by BQP machines but not BPP machines. - There exist functions that are one-way, and even collision resistant, against classical adversaries but are easily inverted quantumly. Similar separations hold for digital signatures and CPA-secure public key encryption (the latter requiring the assumption of a classically CPA-secure encryption scheme). Interestingly, the separation does not necessarily extend to the case of other cryptographic objects such as PRGs. - There are unconditional publicly verifiable proofs of quantumness with the minimal rounds of interaction: for uniform adversaries, the proofs are non-interactive, whereas for non-uniform adversaries the proofs are two message public coin. - Our results do not appear to contradict the Aaronson-Ambanis conjecture. Assuming this conjecture, there exist publicly verifiable certifiable randomness, again with the minimal rounds of interaction. By replacing the random oracle with a concrete cryptographic hash function such as SHA2, we obtain plausible Minicrypt instantiations of the above results. Previous analogous results all required substantial structure, either in terms of highly structured oracles and/or algebraic assumptions in Cryptomania and beyond.

Interactive quantum advantage from any non-local game

Alex Lombardi, MIT, USA

We show a general method of compiling any k-prover non-local game into a single-prover interactive game maintaining the same (quantum) completeness and (classical) soundness guarantees. Our compiler uses a quantum homomorphic encryption scheme as a cryptographic mechanism to (provably) simulate the effect of spatial separation. In this talk, I will describe the compiler at a high level and give an extremely simple proof of its security in the case of the celebrated CHSH game (Clauser, Horne, Shimonyi and Holt, Physical Review Letters 1969). I will then sketch a proof of its security for any non-local game. In conjunction with the rich literature on (entangled) multi-prover non-local games, our compiler gives a broad framework for constructing mechanisms to classically verify quantum advantage. This talk is based on joint work with Yael Kalai, Vinod Vaikuntanathan, and Lisa Yang (

Pseudorandom quantum states, revisited: Improved analysis, new definitions, constructions and cryptographic applications

Prabhanjan Ananth, UCSB, USA

Abstract: Pseudorandom quantum states (PRS) are efficiently computable quantum states that are computationally indistinguishable from Haar random states. PRS has found applications in physics and quantum machine learning. Understanding this object and exploring its applications is an important direction in quantum cryptography. In this talk, I'll discuss the following: - Improved analysis of existing constructions of PRS based on one-way functions. En route, we will present a new method for analyzing Haar random states, - Near tight characterization of PRS with information theoretic security in terms of its output length, - New definitions of PRS that enable the generation of multiple pseudorandom states using the same seed, - Cryptographic applications of pseudorandom quantum states using classical communication via a new tool called verifiable tomography.

On the Heisenberg thought experiment and notions of compatibility

Paolo Perinotti, University of Pavia, Italy

We will analyse two aspects of non-classicality that are connected with Heisenberg's uncertainty principle. The first one is the irreducible disturbance on a system that comes with every observation, while the second one—the real subject of the uncertainty principle—is incompatibility of different physical quantities for the same system. We will formulate and analyse the above features in the wide context of operational probabilistic theories—theories that share with quantum and classical theory the structures describing parallel and sequential composition of processes, but allowing for systems with possibly odd properties. We will provide various conditions for the presence or absence of measurement disturbance and incompatibility. We will discuss, in particular, to what extent these two features are distinctive traits of non-classicality. G. M. D’Ariano, P. Perinotti, A. Tosini, Information and disturbance in operational probabilistic theories, Quantum 4, 363 (2020). G. M. D’Ariano, P. Perinotti, A. Tosini, Incompatibility of observables, channels and instruments in information theories, J. Phys. A: Math. Theor. 55 394006.

Total insecurity of communication via strong converse for quantum privacy amplification

Robert Salzmann, University of Cambridge, UK

Quantum privacy amplification is a central task in quantum cryptography. Given shared randomness, which is initially correlated with a quantum system held by an eavesdropper, the goal is to extract uniform randomness which is decoupled from the latter. The optimal rate for this task is known to satisfy the strong converse property and we provide a lower bound on the corresponding strong converse exponent. In the strong converse region, the distance of the final state of the protocol from the desired decoupled state converges exponentially fast to its maximal value, in the asymptotic limit. We show that this necessarily leads to totally insecure communication by establishing that the eavesdropper can infer any sent messages with certainty, when given very limited extra information. In fact, we prove that in the strong converse region, the eavesdropper has an exponential advantage in inferring the sent message correctly, compared to the achievability region. Additionally we establish the following technical result, which is central to our proofs, and is of independent interest: the smoothing parameter for the smoothed max-relative entropy satisfies the strong converse property. The talk will be based on a joint work with Nilanjana Datta, for more information please see arXiv:2202.11090.

The logo of Kyoto University by Source, Fair use. The logo of the Yukawa Institute for Theoretical Physics.

Latest update on October 21, 2022.