Workshop on Quantum Information, Computation, and Foundation

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

To be held online from September 14 to 18, 2020

Description

The workshop on Quantum Information, Computation, and Foundation 2020 (QICF20) will focus on device independent quantum information processing, 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.

Registration

Registration is closed.

Invited speakers

Program

Organizers

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

Abstracts

Absolutely entangled sets of states

Valerio Scarani, National University of Singapore

The notion of entanglement of quantum states is usually defined with respect to a fixed bipartition. Indeed, a global basis change can always map an entangled state to a separable one. The situation is however different when considering a set of states. We define the notion of an "absolutely entangled set" of quantum states, in which for any possible choice of global basis, at least one of the states in the set is entangled. I'll discuss the physical relevance of the notion and present several examples. Joint work with Pooja Jayachandran, Baichu Yu (NUS), Yu Cai, Jean-Daniel Bancal, Nicolas Brunner (University of Geneva). Reference: https://arxiv.org/abs/2006.07165

Quantum Garbled Circuits

Henry Yuen, University of Toronto

Yao's garbled circuits is the central example of a cryptographic primitive known as randomized encodings, in which a function f and input x can be encoded in such a way that only the value f(x) can be recovered, but nothing else about the function f or x can be learned. Garbled circuits (and randomized encodings more generally) have had numerous applications to secure multiparty computation, obfuscation, zero knowledge protocols, parallel cryptography, complexity theory, and more. In this talk I will introduce the notion of quantum randomized encodings, and will present an instantiation with a quantum analogue of Yao's garbled circuits. Time permitting I will discuss applications of quantum garbled circuits/randomized encodings to secure quantum multiparty computation and obfuscation of quantum circuits. Joint work with Zvika Brakerski (https://arxiv.org/abs/2006.01085).

A hidden variable model for universal quantum computation with magic states on qubits

Robert Raussendorf, University of British Columbia

We show that every quantum computation can be described by Bayesian update of a probability distribution on a finite state space. Negativity in a quasiprobability function is not required, neither in states nor the operations. Our result is consistent with Gleason's Theorem and the PBR theorem. ArXiv:2004.01992v1; joint work with Michael Zurel and Cihan Okay.

Hamiltonian complexity meets derandomization

Alex Grilo, CWI and QuSoft, Amsterdam, The Netherlands

The derandomization of MA, the probabilistic version of NP, is a long standing open question. In this work, we connect this problem to a variant of another major problem: the quantum PCP conjecture. Our connection goes through the surprising quantum characterization of MA by Bravyi and Terhal. They proved the MA-completeness of the problem of deciding whether the groundenergy of a uniform stoquastic local Hamiltonian is zero or inverse polynomial. We show that the gapped version of this problem, i.e. deciding if a given uniform stoquastic local Hamiltonian is frustration-free or has energy at least some constant $epsilon$, is in NP. Thus, if there exists a gap-amplification procedure for uniform stoquastic Local Hamiltonians (in analogy to the gap amplification procedure for constraint satisfaction problems in the original PCP theorem), then MA = NP (and vice versa). Furthermore, if this gap amplification procedure exhibits some additional (natural) properties, then P = RP. We feel this work opens up a rich set of new directions to explore, which might lead to progress on both quantum PCP and derandomization. As a small side result, we also show that deciding if commuting stoquastic Hamiltonian is frustration free is in NP. Joint work with Dorit Aharonov.

Reinforcement Learning with Neural Networks for Quantum Multiple Hypothesis Testing

Sarah Brandsen, Duke University, U.S.A.

Reinforcement learning with neural networks (RLNN) has recently demonstrated great promise for many problems, including some problems in quantum information theory. In this work, we apply RLNN to quantum hypothesis testing, where one designs measurements that can distinguish between multiple quantum states while minimizing the error probability. In the case where the candidate states correspond to a quantum system with many qubit subsystems, implementing the optimal measurement on the entire system may be impractical. Thus, we develop locally-adaptive measurement strategies that are experimentally feasible as only one quantum subsystem is measured in each round. RLNN is used to find the optimal local measurement protocol for arbitrary sets of tensor product quantum states. Numerical results for the network performance are shown, the gap between the RLNN performance and optimal collective (non-local) measurement is investigated. Finally, we introduce a min-entropy based locally adaptive protocol, and compare this protocol to RLNN as well as the optimal collective measurement.

Information and disturbance in operational probabilistic theories

Alessandro Tosini, University of Pavia, Italy

Any measurement is intended to provide information on a system, namely knowledge about its state. However, we learn from quantum theory that it is generally impossible to extract information without disturbing the state of the system or its correlations with other systems. In this paper we address the issue of the interplay between information and disturbance for a general operational probabilistic theory. The traditional notion of disturbance considers the fate of the system state after the measurement. However, the fact that the system state is left untouched ensures that also correlations are preserved only in the presence of local discriminability. Here we provide the definition of disturbance that is appropriate for a general theory. Moreover, since in a theory without causality information can be gathered also on the effect, we generalise the notion of no-information test. We then prove an equivalent condition for no-information without disturbance - atomicity of the identity - namely the impossibility of achieving the trivial evolution - the identity - as the coarse-graining of a set of non trivial ones. We prove a general theorem showing that information that can be retrieved without disturbance corresponds to perfectly repeatable and discriminating tests. Based on this, we prove a structure theorem for operational probabilistic theories, showing that the set of states of any system decomposes as a direct sum of perfectly discriminable sets, and such decomposition is preserved under system composition. As a consequence, a theory is such that any information can be extracted without disturbance only if all its systems are classical. Finally, we show via concrete examples that no-information without disturbance is independent of both local discriminability and purification.

Isoentangled Mutually Unbiased Bases, Mixed-states t-designs and symmetric informationally complete measurements

Karol Zyczkowski, Institute of Physics, Jagiellonian University, Cracow and Center for Theoretical Physics, PAS, Warsaw

An Euclidean design is a finite set of points in R^n with certain approximation properties. This concept generalizes the notion of a spherical t-design k, which consists of a certain number M of points belonging to a sphere S_(n−1) and selected in such a way that for any polynomial f of order t the mean values of first t moments averaged over the set k coincide with the averages over the sphere. Taking the corresponding set of normalized pure quantum states |psi_j> one arrives at a projective t-design - a construction useful in quantum theory.

We introduce a related notion of a mixed-states t-design, which consist of a finite number of M density matrices of a fixed dimension n, such that the mean value of any polynomial function f of their spectra of order not exceeding t agrees with the integral of f over the entire set Omega_n of mixed quantum states of size n with respect to the flat, Hilbert-Schmidt measure. We establish necessary and sufficient conditions for a given set of density matrices to form a t-design [1] and demonstrate that any projective t-design on a composed Hilbert space H_n x H_n yields by partial trace a mixed states t-design in the set Omega_n.

In particular, the standard symmetric informationally complete measurement (SIC POVM) in H_4 leads to a configuration of M = 8 density matrices forming a regular cube inside the Bloch ball Omega_2 which forms a 2-design. Furthermore, we construct a set of five isoentangled MUBs in H_4, consisting of states with the same degree of entanglement. Performing partial trace on any of both subsystems leads to 20 one-qubit mixed states which form a regular dodecahedron inside the Bloch ball - an exemplary 3-design [1]. A suitably rescaled mixed design is shown to be related to the Elegant Joint Measurement, which can be obtained by partial trace of an orthogonal basis in a bipartite space H_n x H_n with optimal single-sided state distinguishability [2].

[1] J. Czartowski, D. Goyeneche, M. Grassl and K. Zyczkowski, Iso-entangled mutually unbiased bases, symmetric quantum measurements and mixed-state designs, Phys. Rev. Lett. 124, 090503 (2020).

[2] J. Czartowski and K. Zyczkowski, Bipartite quantum measurements with optimal single-sided distinguishability, 2020, to appear.

Non-interactive verification of quantum computations

Gorjan Alagic, University of Maryland and NIST, U.S.A.

In a recent breakthrough, Mahadev constructed an interactive protocol that enables a purely classical party to delegate any quantum computation to an untrusted quantum prover. In this work, we show that this same task can in fact be performed non-interactively and in zero-knowledge. Our protocols result from a sequence of significant improvements to the original four-message protocol of Mahadev. We begin by making the first message instance-independent and moving it to an offline setup phase. We then establish a parallel repetition theorem for the resulting three-message protocol, with an asymptotically optimal rate. This, in turn, enables an application of the Fiat-Shamir heuristic, eliminating the second message and giving a non-interactive protocol. Finally, we employ classical non-interactive zero-knowledge (NIZK) arguments and classical fully homomorphic encryption (FHE) to give a zero-knowledge variant of this construction. This yields the first purely classical NIZK argument system for QMA, a quantum analogue of NP. We establish the security of our protocols under standard assumptions in quantum-secure cryptography. Specifically, our protocols are secure in the Quantum Random Oracle Model, under the assumption that Learning with Errors is quantumly hard. The NIZK construction also requires circuit-private FHE.

Discriminating between unitary quantum processes

Nilanjana Datta, University of Cambridge, U.K.

Discriminating between unknown objects in a given set is a fundamental task in experimental science. Suppose you are given a quantum system which is in one of two given states with equal probability. Determining the actual state of the system amounts to doing a measurement on it which would allow you to discriminate between the two possible states. It is known that unless the two states are mutually orthogonal, perfect discrimination is possible only if you are given arbitrarily many identical copies of the state. In this talk we consider the task of discriminating between quantum processes, instead of quantum states. In particular, we discriminate between a pair of unitary operators acting on a quantum system whose underlying Hilbert space is possibly infinite-dimensional. We prove that in contrast to state discrimination, one needs only a finite number of copies to discriminate perfectly between the two unitaries. Furthermore, no entanglement is needed in the discrimination task. The measure of discrimination is given in terms of the energy-constrained diamond norm and one of the key ingredients of the proof is a generalization of the Toeplitz-Hausdorff Theorem in convex analysis. Moreover, we employ our results to study a novel type of quantum speed limits which apply to pairs of quantum evolutions. This work was done jointly with Simon Becker (Cambridge), Ludovico Lami (Ulm) and Cambyse Rouze (Munich).

Stochastic Local Operations with Classical Communication of Absolutely Maximally Entangled States

Adam Burchardt, Jagiellonian University, Poland

Absolutely Maximally Entangled (AME) states are maximally entangled for every bipartition of the system. They are crucial resources for various quantum information protocols. We present techniques for verifying either two AME states are equivalent concerning Stochastic Local Operations and Classical Communication (SLOCC). The conjecture that for a given multipartite quantum system all AME states are SLOCC-equivalent is falsified. We also show that the existence of AME states with minimal support of 6 or more particles results in the existence of infinitely many such non-SLOCC-equivalent states. Moreover, we present AME states which are not SLOCC-equivalent to the existing AME states with minimal support.

Storage and retrieval of a unitary transformation

Alessandro Bisio, University of Pavia, Italy

Suppose we have limited access to a quantum transformation. Then we may want to store it into a quantum memory and retrieve it later. In this way, we could still apply the transformation to any state once we cannot use it directly anymore. This can also be valuable if we would like to transmit the transformation to a remote party by just transmitting a state, without the need of transferring the device. Quantum theory does not allow for a storage-and-retrieval procedure which is both deterministic and perfect (i.e. without errors). Therefore, there are two alternative ways to address this problem. On one hand, we may require a deterministic procedure with the best approximate performance. One the other hand, we may want to perfectly retrieve the unknown transformation but with some probability of failure. In this talk we consider the case of storage and retrieval of an unknown unitary transformation on d-dimensional quantum system from a finite number N of examples. In the deterministic and approximate scenario, the optimal performances are achieved by a measure-and-prepare strategy that does not make use of any quantum memory. In the probabilistic and perfect scenario, the optimal success probability is N/(N-1+d^2). These results closely relate to the optimal alignment of reference frames and probabilistic port-based teleportation.

Relativistic and Non-Local Zero-Knowledge

Claude Crépeau, McGill University, Canada

Since the end of the 1980's interactive proofs have been considered in the multi-prover setting. The original work defined the provers as "local" participants. Since then, the soundness of these proofs has been analyzed in the light of Quantum Non-Locality, and general No-Signalling. Relativistic Bit commitment schemes have been introduced to achieve the Zero-Knowledge aspect of these proofs. However, up to now, no consideration about Non-Locality has been explored on the Zero-Knowledge part. This work introduces the notions of Relativistic Zero-Knowledge and, more generally, Non-Local Zero-Knowledge where not only several provers but also several verifiers receive information from their individual counterpart prover. As an application, we show that certain multi-prover Zero-Knowledge proofs sound against local or entangled provers can be simulated by No-Signalling verfiers/simulators. Such a proof would therefore be more "Zero-Knowledge" than previous ones under the precise definition we introduce. Joint work with Aly Ibrahim and Nan Yang

General framework for verifying pure quantum states in the adversarial scenario

Huangjun Zhu, Fudan University, China

Bipartite and multipartite entangled states are of central interest in quantum information processing and foundational studies. Efficient verification of these states, especially in the adversarial scenario, is a key to various applications, including quantum computation, quantum simulation, and quantum networks. However, little is known about this topic in the adversarial scenario. Here we initiate a systematic study of pure-state verification in the adversarial scenario. In particular, we introduce a general method for determining the minimal number of tests required by a given strategy to achieve a given precision. In the case of homogeneous strategies, we can even derive an analytical formula. Furthermore, we propose a general recipe to verifying pure quantum states in the adversarial scenario by virtue of protocols for the nonadversarial scenario. Thanks to this recipe, the resource cost for verifying an arbitrary pure state in the adversarial scenario is comparable to the counterpart for the nonadversarial scenario, and the overhead is at most three times for high-precision verification. Our recipe can readily be applied to efficiently verify bipartite pure states, stabilizer states, hypergraph states, weighted graph states, and Dicke states in the adversarial scenario, even if only local projective measurements are accessible. Joint work with Masahito Hayashi, PRL 123, 260504 (2019); PRA 100, 062335 (2019).

On public verifiability for secure delegated quantum computation

Takeshi Koshiba, Waseda Univesity, Japan

Secure delegated quantum computation (SDQC) is a protocol between a client Alice and a server Bob. Alice would like Bob to delegate her task to evaluate a function on her input with a quantum algorithm for the evaluation. As a security requirement, Alice does not reveal her input/output and even her algorithm to Bob. It is known that SDQC is possible in the unconditional setting and many protocols have been proposed in the literature. On the other hand, Bob might deviate from the protocol specification. Nonetheless, Bob may claim that he competes his task as required. Verifiability guarantees that such an illegal behavior by Bob can be detected by Alice. Alice can notice Bob's dishonesty but it is difficult to prove Bob's dishonesty. To resolve this problem, the notion of public verifiability would be important. In this talk, we will discuss possibilities and limitations of public verifiability of SDQC.

Is Unitarity an option?

Giacomo Mauro D'Ariano, University of Pavia, Italy

For historical reasons it is often assumed that in quantum theory transformations undergone by closed systems are unitary, whereas those undergone by open systems are trace-non-increasing completely-positive maps (CP maps for short). Similarly, it is assumed that the state of an isolated system is pure. It is a theorem that any mixed state can be purified, and any CP map can be achieved by a unitary interaction followed by a von Neumann measurement. However, this does not mean that necessarily a mixed state is "actually" the marginal of a pure state, and that an irreversible transformation is actually achieved through a unitary one, since such purifications are not unique, and in addition their physical existence is provably unfalsifiable. We conclude that, contrarily to the above common belief, quantum theory is closed and logically consistent without any purification ontology. This rules out all paradoxes (most remarkably, the information paradox), and make popular interpretations as the "many-world" exegesis of elements not needed to the completeness of the theory. Unitarity maintains its role of "symmetry" of the theory.

Optimal hiding of quantum information

Francesco Buscemi, Nagoya University, Japan

Decoupling is the task of erasing the correlations that an object system, accessible to us, has established with a remote reference system. This task has fundamental applications in a wide number of fields, such as quantum secure communication, thermodynamics, and black-hole radiation. When faced with the problem of erasing correlations, the direct approach is "to dump" them in the environment, that is, to hand them over to an eavesdropper. A variant of decoupling is quantum hiding, where the goal is again to decouple the system from the reference, but this time maintaining also its local environment decoupled from the reference [Braunstein, Pati; PRL 2007].

Here, by building upon the paradigm of private quantum decoupling [Buscemi; NJP 2009], I formalize the information-theoretic task of optimal quantum hiding and provide a single-letter formula for its optimal rate in the asymptotic i.i.d. setting. It turns out that the total amount of correlations present in the initial state is divided into "extrinsic" (hidable) and "intrinsic" (non hidable) ones, the latter being equal to the coherent information (which is thus equipped with a new operational interpretation). Connections with entanglement theory are finally discussed.

Morphophoric quantum measurements, generalised qplexes, and 2-designs

Anna Szymusiak, Jagiellonian University, Poland

We study the class of generalised quantum measurements (POVMs) with the property that the image of the set of quantum states under the measurement map transforming states into probability distributions is similar to this set and call such measurements morphophoric. This leads to the generalisation of the notion of a qplex, where SIC-POVMs are replaced by the elements of the much larger class of morphophoric POVMs, containing in particular 2-design (rank-1 and equal-trace) POVMs. The intrinsic geometry of a generalised qplex is the same as that of the set of quantum states, so we explore its external geometry, investigating, inter alia, the algebraic and geometric form of the inner (basis) and the outer (primal) polytopes between which the generalised qplex is sandwiched. In particular, we examine generalised qplexes generated by MUB-like 2-design POVMs utilising their graph-theoretical properties. Joint work with Wojciech Słomczyński (arXiv:1911.12456, to be published in Quantum).

Benchmarking quantum technologies

Jens Eisert, Free University of Berlin, Germany

At the same time as the development of quantum technologies progresses rapidly, new demands concerning the certification of their operation emerge. A question relevant for the application of various quantum technologies consequently is how the user can ensure the correct functioning of the quantum devices [1]. In a number of instances, specifically in quantum simulation and quantum computing, challenges in appropriately benchmarking components or entire protocols constitute a widely acknowledged bottleneck. This talk will suggest several new takes to the problem at hand: We will see how data from SPAM-robust randomized benchmarking [2] can be used to perform process tomography of quantum gates in an experimentally-friendly and provably sample optimal fashion [3], making use of a machinery of compressed sensing and exploiting structure - that is to say, the components of a quantum circuit. We will see how quantum states can be characterizes provably even with imperfect detectors in what could be called semi-device-dependent tomography [4]. The issue becomes more challenging when one aims at certifying the functioning of an entire device. We will look at limitations to black-box verification for sampling problems that show a quantum advantage or "supremacy" [5], will have a fresh look at Hamiltonian learning [6] and will see that in some instances [7], one can ironically certify the correctness of a device even if one cannot efficiently predict its performance.

[1] Quantum certification and benchmarking, J. Eisert, D. Hangleiter, N. Walk, I. Roth, D. Markham, R. Parekh, U. Chabaud, E. Kashefi, Nature Reviews Physics 2, 382-390 (2020). [2] Randomized benchmarking for individual quantum gates, E. Onorati, A. H. Werner, J. Eisert, Phys. Rev. Lett. 123, 060501 (2019). [3] Recovering quantum gates from few average gate fidelities, I. Roth, R. Kueng, S. Kimmel, Y.-K. Liu, D. Gross, J. Eisert, M. Kliesch, Phys. Rev. Lett. 121, 170502 (2018). [4] Semi-device-dependent blind quantum tomography, I. Roth, J. Wilkens, D. Hangleiter, J. Eisert, arXiv:2006.03069 (2020). [5] Sample complexity of device-independently certified quantum supremacy, D. Hangleiter, M. Kliesch, J. Eisert, C. Gogolin, Phys. Rev. Lett. 122, 210502 (2019). [6] In preparation (2020). [7] J. Haferkamp, D. Hangleiter, A. Bouland, B. Fe?erman, J. Eisert, and J. Bermejo-Vega, arXiv:1908.08069 (2019).

Non-interactive zero-knowledge arguments for QMA, with preprocessing

Andrea Coladangelo, UC Berkeley, USA

Zero-knowledge proofs for QMA have first been studied in a work of Broadbent et al (FOCS'16). There, the authors show that any language in QMA has an (interactive) zero-knowledge proof. In this talk, I will describe an idea, based on quantum teleportation, to remove interaction at the cost of adding an instance-independent preprocessing step. Assuming the Learning With Errors problem is hard for quantum computers, the resulting protocol is a non-interactive zero-knowledge argument for QMA, with a preprocessing step that consists of (i) the generation of a Common Reference String and (ii) a single (instance-independent) quantum message from the verifier to the prover.

Security Limitations of Classical-Client Delegated Quantum Computing

Atul Mantri, University of Maryland, USA

Secure delegated quantum computing allows a computationally weak client to outsource an arbitrary quantum computation to an untrusted quantum server in a privacy-preserving manner. One of the promising candidates to achieve classical delegation of quantum computation is classical-client remote state preparation, where a client remotely prepares a quantum state using a classical channel. In this talk, I will present some recent (impossibility and possibility) results concerning the security of remote state preparation and its application - universal blind quantum computing - using the constructive cryptography framework and game-based model. The talk will be based on joint work with C. Badertscher, A. Cojocaru, L. Colisson, E. Kashefi, D. Leichtle, P. Wallden (https://arxiv.org/abs/2007.01668, to be published in Asiacrypt 2020)

Cellular automata in operational probabilistic theories

Paolo Pernotti, University of Pavia, Italy

We extend the notion of a Quantum Cellular Automaton to general Operational Probabilistic Theories, and discuss in detail the concept of causal influence under a reversible evolution. We then introduce the property of homogeneity, in a framework where space-time is not a primitive concept. We show how a Cayley graph structure universally and naturally follows from homogeneity, thus proving that the latter can be formulated in the absence of the structure of a translation symmetry group, and that such a symmetry can be recovered as a consequence of the principle itself. We then discuss locality, and its main consequences.

Certification of many-body quantum states

Antonio Acin, ICFO Barcelona, Spain

Detecting relevant quantum properties of many-body quantum states is a challenging problem because of the exponential number of parameters needed to specify them. We discuss two approaches to address this challenge: first, we introduce a renormalization-inspired method for the detection of relevant quantum properties of quantum states, such as entanglement and Bell nonlocality, in terms of what we call connector tensor networks [1]. Then, we consider the entanglement marginal problem, that consists in deciding whether a number of reduced density matrices are compatible with an overall separable quantum state. To tackle this problem, we propose hierarchies of semidefinite programming relaxations of the set of quantum state marginals admitting a fully separable extension [2].

[1] M. Navascués, S. Singh, A. Acín, Connector tensor networks: a renormalization-type approach to quantum certification, Phys. Rev. X 10, 021064 (2020)

[2] M. Navascués, F. Baccari, A. Acín, Entanglement marginal problems, arXiv: 2006.09064

Quantum dynamical entropy and iterated function systems in quantum state space

Wojciech Słomczyński, Jagiellonian University, Poland

Joint work with Anna Szczepanek.

Consider successive measurements performed on a finite-dimensional quantum system which between two subsequent measurements (described by a POVM) undergoes evolution governed by a unitary operator. Such an intertwined procedure can be represented by a partial iterated function system acting on the set of quantum states and, in consequence, by a Markov chain on this set. Then, the sequences of emitted symbols, which are interpreted as measurement outcomes, can be modelled by a hidden Markov chain. Our aim is to quantify the potential of the unitary dynamics governing the system to generate random sequences of symbols. To achieve this end, we employ the notion of quantum dynamical entropy (also known as quantum entropy rate), which for hidden Markov chains can be expressed by the famous Blackwell integral formula.

For rank-1 POVMs, a closed-form expression for dynamical entropy can be easily derived. We show how to introduce the measurement-independent definition of dynamical entropy in this case, as well as distinguish and characterize the class of chaotic unitaries for which the entropy attains maximal value. For POVMs that contain operators of ranks higher than 1, no closed-form formula for dynamical entropy is known. We investigate a system analysed earlier by Crutchfield & Wiesner, where dynamics is given by a specific unitary operator of dimension 3 and the measurement by a PVM containing one projector of rank 1 and the other of rank 2. We classify the respective Markov chains in all similar systems and calculate their entropy using the Blackwell formula.

Szczepanek, A., Quantum Dynamical Entropy of Unitary Operators in Finite-dimensional State Spaces, PhD Dissertation, Jagiellonian University, 2019; WS, Dynamical Entropy, Markov Operators, and Iterated Function Systems. Wydawnictwo UJ, Kraków, 2003; WS, Szczepanek A., Quantum dynamical entropy, chaotic unitaries and complex Hadamard matrices, IEEE Trans. Inform. Theory 63 (2017), 7821-7831; WS, Szczepanek, A., Orthogonal projections on hyperplanes intertwined with unitaries, arXiv:2005.13658 [quant-ph].

Towards quantum advantage for topological data analysis

Vedran Dunjko, Leiden University, The Netherlands

A significant aspect of quantum machine learning (QML) relying on quantum linear algebra ideas has been hailed as a potential source of exponential speedups over classical algorithms. However, a recent series of ``dequantization" results, which use clever classical sampling methods, have removed the possibility of strict exponential speed-ups for many machine learning and related quantum-linear-algebraic approaches. However, not all such algorithms can directly be de-quantized using these recent classical methods. One example of such a QML algorithm, that has not (yet) been dequantized is the quantum algorithm for topological data analysis, introduced by Lloyd, Garnerone and Zanardi. Can exponential separations for this problem be proven, at least up to some more established complexity-theoretic assumptions? Further, does this algorithm have a chance of being extended to other problems and run on near-term devices? In this talk we will provide evidence that the problem of topological data analysis, and certain other related more general problems, are truly out of reach for classical computers. Towards the end of the talk we will also consider the suitability of the quantum topological data analysis algorithm for near-term implementations, and discuss the possibility of it being one of the first quantum "NISQ killer apps". Based on arXiv:2005.02607

Impossibility of Quantum Copy-Protection and Secure Software Leasing

Rolando La Placa, MIT, USA

We introduce the notion of secure software leasing (SSL): this allows for an authority to lease software to a third party with the security guarantee that after the lease expires, the third party can no longer produce any functionally equivalent software (including the original software) that can be run on the same platform. While impossible to achieve classically, this opens up the possibility of using quantum tools to realize this notion. In this work, we initiate a formal study of this notion and present both positive and negative results under quantum hardness of classical cryptographic assumptions. (1) Negative Result: We prove that it is impossible to construct SSL schemes for an arbitrary class of quantum unlearnable functions. In particular, our impossibility result also rules out quantum copy-protection [Aaronson CCC'09] for any class of quantum unlearnable functions; resolving an open problem on the possibility of constructing copy-protection for arbitrary quantum unlearnable circuits. Our techniques also rule out the existence of quantum VBB for classical circuits, answering an open problem posed by [Alagic and Fefferman arXiv'16]. Along the way, we introduce a notion called de-quantizable circuits and present the first construction of this notion which may be of independent interest. (2) Positive Result: On the other hand, we show that we can realize SSL for a subclass of evasive circuits (that includes natural implementations of point functions, conjunctions with wild cards, and affine testers).

Quantum money and some of its extensions

Or Sattath, Ben-Gurion University, Israel

One of the unique aspects of quantum mechanics is the no-cloning theorem. This theorem has a very direct application in quantum cryptography: quantum money is very similar to the cash we use, but in addition, it is physically impossible to forge. In this talk, I will discuss quantum money, and some of its extensions (quantum coins, semi quantum money, tokens for digital signatures, quantum copy protection, and quantum lightning). If time permits, I will also describe a way to integrate quantum money in a system such as Bitcoin. Based on the following works (with collaborators): - A Quantum Money Solution to the Blockchain Scalability Problem (QCrypt'20; Quantum 4, 297 (2020)). - Almost Public Quantum Coins (arXiv:2002.12438) - Semi-Quantum Money (arXiv:1908.08889, AFT'19). - Quantum Tokens for Digital Signatures (arXiv:1609.09047, QCrypt 2017).

Quantum encryption schemes for uncloneability and certified deletion

Anne Broadbent, University of Ottawa, Canada

Quantum information is well-known to achieve cryptographic feats that are unattainable using classical information alone. Here, we add to this repertoire by studying quantum encryption schemes for classical information. We show that, using conjugate coding for the encoding of a classical message enables cryptographic primitives that are trivially impossible classically. The first property is 'uncloneability', meaning that it is not possible for two adversarial parties to split the ciphertext such that, after the key is revealed, both parties are able to correctly decrypt (this result is achieved in the quantum random oracle model). The second property is 'certified deletion', meaning that given a ciphertext, a recipient can delete the ciphertext, and prove this fact to the originator, via a classical message. Based on joint work with Sebastien Lord and Rabib Islam.

Latest update on September 25, 2020.