**Kamil Korzekwa****, Zbigniew Puchała, Marco Tomamichel and Karol Życzkowski. Encoding classical information into quantum resources**

**Abstract: **We introduce and analyse the problem of encoding classical
information into different resources of a quantum state. More precisely, we
consider a general class of communication scenarios characterised by encoding
operations that commute with a unique resource destroying map and leave free
states invariant. Our motivating example is given by encoding information into
coherences of a quantum system with respect to a fixed basis (with unitaries
diagonal in that basis as encodings and the decoherence channel as a resource
destroying map), but the generality of the framework allows us to explore
applications ranging from super-dense coding to thermodynamics. For any state,
we find that the number of messages that can be encoded into it using such
operations in a one-shot scenario is upper-bounded in terms of the information
spectrum relative entropy between the given state and its version with erased
resources. Furthermore, if the resource destroying map is a twirling channel
over some unitary group, we find matching one-shot lower-bounds as well. In the
asymptotic setting where we encode into many copies of the resource state, our
bounds yield an operational interpretation of resource monotones such as the
relative entropy of coherence and its corresponding relative entropy variance.

**João Fernando Doriguello and Ashley Montanaro. Exponential quantum communication reductions from generalizations of the Boolean Hidden Matching problem**

**Abstract: **In this work we revisit the Boolean Hidden Matching
communication problem, which was the first communication problem in the one-way
model to demonstrate an exponential classical-quantum communication separation.
In this problem, Alice’s bits are matched into pairs according to a partition
that Bob holds. These pairs are compressed using a Parity function and it is
promised that the final bit-string is equal either to another bit-string Bob
holds, or its complement. The problem is to decide which case is the correct
one. Here we generalize the Boolean Hidden Matching problem by replacing the
parity function with an arbitrary function $f$. Efficient communication
protocols are presented depending on the sign-degree of $f$. If its sign-degree
is less than or equal to 1, we show an efficient classical protocol. If its
sign-degree is less than or equal to $2$, we show an efficient quantum
protocol. We then completely characterize the classical hardness of all
symmetric functions $f$ of sign-degree greater than or equal to $2$, except for
one family of specific cases. We also prove, via Fourier analysis, a classical
lower bound for any function $f$ whose pure high degree is greater than or
equal to $2$. Similarly, we prove, also via Fourier analysis, a quantum lower
bound for any function $f$ whose pure high degree is greater than or equal to
$3$. These results give a large family of new exponential classical-quantum
communication separations.

**Nikhil Mande****, ****Justin Thaler**** and ****Shuchen Zhu****. Improved Approximate Degree Bounds For k-distinctness**

**Abstract: **An open problem that is widely regarded as one of the most
important in quantum query complexity is to resolve the quantum query
complexity of the k-distinctness function on inputs of size N. While the case
of k=2 (also called Element Distinctness) is well-understood, there is a
polynomial gap between the known upper and lower bounds for all constants
k>2.

Specifically, the best known upper bound is O(N^{(3/4)-1/(2^{k+2}-4)}) (Belovs,
FOCS 2012), while the best known lower bound for k >= 2 is Omega(N^{2/3} +
N^{(3/4)-1/(2k)}) (Aaronson and Shi, J.~ACM 2004; Bun, Kothari, and Thaler,
STOC 2018).

For any constant k >= 4, we improve the lower bound to Omega(N^{(3/4)-1/(4k)}).
This yields, for example, the first proof that 4-distinctness is strictly
harder than Element Distinctness. Our lower bound applies more generally to
approximate degree.

As a secondary result, we give a simple construction of an approximating
polynomial of degree O(N^{3/4}) that applies whenever k <= polylog(N).

**Ulysse Chabaud, Tom Douce, Frédéric Grosshans, Elham Kashefi and Damian Markham. Building trust for continuous variable quantum states**

**Abstract: **In this work we develop new methods for the characterisation
of continuous variable quantum states using heterodyne measurement in both the
trusted and untrusted settings.

First, building on quantum state tomography with heterodyne detection, we
introduce a reliable method

for continuous variable quantum state certication, which directly yields the
elements of the density

matrix of the state considered and analytical condence intervals. This method
neither needs

mathematical reconstruction of the data, nor discrete binning of the sample
space, and uses a single

Gaussian measurement setting. Second, beyond quantum state tomography and
without its identical copies

assumption, we promote our reliable tomography method to a general efficient
protocol for verifying continuous

variable pure quantum states with Gaussian measurements against fully malicious
adversaries, i.e.

making no assumptions whatsoever on the state generated by the adversary. These
results are

obtained using a new analytical estimator for the expected value of any operator
acting on a

continuous variable quantum state with bounded support over the Fock basis,
computed with samples

from heterodyne detection of the state.

**Dina Abdelhadi and ****Joseph M. Renes****. Second-order asymptotics of quantum data compression and state merging**

**Abstract: **Recently, Anshu et al. introduced “partially” smoothed information measures and used them to derive tighter bounds for several information-processing tasks, including quantum state merging and privacy amplification against quantum adversaries [arXiv:1807.05630 [quant-ph]]. Yet, a tight second-order asymptotic expansion of the partially
smoothed conditional min-entropy in the i.i.d. setting remains an open
question. Here we establish the second-order term in the expansion for pure
states, and find that it differs from that of the original “globally”
smoothed conditional min-entropy. Remarkably, this reveals that the
second-order term is not uniform across states, since for other classes of
states the second-order terms for partially and globally smoothed quantities
coincide. In view of the tight bounds on the entanglement cost of state merging
in terms of the partially-smoothed conditional min-entropy by Anshu et al.,
this indicates that the second-order asymptotic rate for that task will not
separate so neatly into a term depending on the state (the variance) and a term
depending on the error (the quantile). Finally, by relating the task of quantum
compression to that of quantum state merging, our derived ex- pansion allows us
to determine the second-order asymptotic expansion of the optimal rate of
quantum data compression. This closes a gap in the bounds determined by Datta
and Leditzky [IEEE Trans. Inf. Theory 61, 582 (2015)], and shows that the
straightforward compression protocol of cutting off the eigenspace of least
weight is indeed asymptotically optimal at second order.

**Paul Webster and Stephen Bartlett. Fault-tolerant quantum gates with defects in topological stabiliser codes**

**Abstract: **Braiding defects in topological stabiliser codes has been
widely studied as a promising approach to fault-tolerant quantum computing.
Here, we explore the potential and limitations of such schemes in codes of all
spatial dimensions. We prove that a universal gate set for quantum computing
cannot be realised by supplementing locality-preserving logical operators with
defect braiding, even in more than two dimensions. However, notwithstanding
this no-go theorem, we demonstrate that higher dimensional defect-braiding
schemes have the potential to play an important role in realising
fault-tolerant quantum computing. Specifically, we present an approach to
implement the full Clifford group via braiding in any code possessing twist
defects on which a fermion can condense. We explore three such examples in
higher dimensional codes, specifically: in self-dual surface codes; the three
dimensional Levin-Wen fermion model; and the checkerboard model. Finally, we
show how our no-go theorems can be circumvented to provide a universal scheme
in three-dimensional surface codes without magic state distillation.

**Julio Carlos Magdalena de la Fuente, Nicolas Tarantino and Jens Eisert. Non-Pauli Stabilizers from Twisted Quantum Doubles**

**Abstract: **It has long been known that long-ranged entangled
topological phases can be exploited to protect quantum information against
unwanted local errors. Indeed, conditions for intrinsic topological order are
reminiscent of criteria for faithful quantum error correction. At the same
time, the promise of using general topological orders for practical error
correction remains largely unfulfilled to date. In this work, we significantly
contribute to establishing such a connection by showing that Abelian twisted
quantum double models can be used for quantum error correction. By exploiting
the group cohomological data sitting at the heart of these lattice models, we
transmute the terms of these Hamiltonians into full-rank, pairwise commuting
operators, defining commuting stabilizers. The resulting codes are defined by
non-Pauli commuting stabilizers, with local systems that can either be qubits
or higher dimensional quantum systems. Thus, this work establishes a new
connection between condensed matter physics and quantum information theory, and
constructs tools to systematically devise new topological quantum error
correcting codes beyond toric or surface code models.

**Tony Metger and Thomas Vidick. Self-testing of a single quantum device under computational assumptions**

**Abstract: **Self-testing is a method to characterise an arbitrary
quantum system based only on its classical input-output correlations. This
usually requires the assumption that the system’s state is shared among
multiple parties that only perform local measurements and cannot communicate.
Here, we replace the setting of multiple non-communicating parties, which is
difficult to enforce in practice, by a single computationally bounded party.
Specifically, we construct a protocol that allows a classical verifier to
robustly certify that a single computationally bounded quantum device must have
prepared a Bell pair and performed single-qubit measurements on it, up to a
change of basis applied to both the device’s state and measurements. This means
that under computational assumptions, the verifier is able to certify the
presence of entanglement inside a single quantum device. We achieve this using
techniques introduced by Brakerski et al. (2018) and Mahadev (2018) which allow
a classical verifier to constrain the actions of a quantum device assuming the
device does not break post-quantum cryptography.

**Taisuke Izumi, ****Francois Le Gall**** and ****Frederic Magniez****. Quantum Distributed Algorithm for Triangle Finding in the CONGEST Model**

**Abstract: **This paper considers the triangle finding problem in the
CONGEST model of distributed computing. Recent works by Izumi and Le Gall
(PODC’17), Chang, Pettie and Zhang (SODA’19) and Chang and Saranurak (PODC’19)
have successively reduced the classical round complexity of triangle finding
(as well as triangle listing) from the trivial upper bound $O(n)$ to $\tilde
O(n^{1/3})$, where~$n$ denotes the number of vertices in the graph. In this
paper we present a quantum distributed algorithm that solves the triangle
finding problem in $\tilde O(n^{1/4})$ rounds in the CONGEST model. This gives
another example of quantum algorithm beating the best known classical
algorithms in distributed computing. Our result also exhibits an interesting phenomenon:
while in the classical setting the best known upper bounds for the triangle
finding and listing problems are identical, in the quantum setting the round
complexities of these two problems are now $\tilde O(n^{1/4})$ and $\tilde
\Theta(n^{1/3})$, respectively. Our result thus shows that triangle finding is
easier than triangle listing in the quantum CONGEST model.

**Anne Broadbent**** and Sébastien Lord. Uncloneable Quantum Encryption via Oracles**

**Abstract: **Quantum information is well-known to achieve cryptographic
feats that are unattainable using classical information alone. Here, we add to
this repertoire by introducing a new cryptographic functionality called
uncloneable encryption. This functionality allows the encryption of a classical
message such that two collaborating but isolated adversaries are prevented from
simultaneously recovering the message, even when the encryption key is
revealed. Clearly, such functionality is unattainable using classical
information alone.

We formally define uncloneable encryption, and show how to achieve it using
Wiesner’s conjugate coding, combined with a quantum-secure pseudorandom
function (qPRF). Modelling the qPRF as an oracle, we show security by adapting
techniques from the quantum one-way-to-hiding lemma, as well as using bounds
from quantum monogamy-of-entanglement games.

**Anurag Anshu. Improved local spectral gap thresholds for lattices of finite dimension**

**Abstract: **Knabe’s theorem lower bounds the spectral gap of a one
dimensional frustration-free local hamiltonian in terms of the local spectral
gaps of finite regions. It also provides a local spectral gap threshold for
hamiltonians that are gapless in the thermodynamic limit, showing that the
local spectral gap much scale inverse linearly with the length of the region
for such systems. Recent works have further improved upon this threshold,
tightening it in the one dimensional case and extending it to higher
dimensions. Here, we show a local spectral gap threshold for frustration-free
hamiltonians on a finite dimensional lattice, that is optimal up to a constant
factor that depends on the dimension of the lattice. Our proof is based on the
detectability lemma framework and uses the notion of coarse-grained hamiltonian
(introduced in [Phys. Rev. B 93, 205142]) as a link connecting the (global)
spectral gap and the local spectral gap.

**Jonas Helsen, Francesco Battistel and Barbara Terhal. Spectral Quantum Tomography**

**Abstract: **We introduce spectral quantum tomography, a simple method to
extract the eigenvalues of a noisy few-qubit gate, represented by a
trace-preserving superoperator, in a SPAM-resistant fashion, using low
resources in terms of gate sequence length. The eigenvalues provide detailed
gate information, supplementary to known gate-quality measures such as the gate
fidelity, and can be used as a gate diagnostic tool. We apply our method to
one- and two-qubit gates on two different superconducting systems available in
the cloud, namely the QuTech Quantum Infinity and the IBM Quantum Experience.
We discuss how cross-talk, leakage and non-Markovian errors affect the
eigenvalue data.

**Lucas Brady, Christopher Baldwin, Aniruddha Bapat, Alexey Gorshkov and Yaroslav Kharkov. Optimal Protocols in Quantum Annealing and QAOA Problems**

**Abstract: **Quantum Annealing and the Quantum Approximate Optimization
Algorithm (QAOA) are both instances of the same control problem in which a
combination of two Hamiltonians is applied to minimize the energy of a quantum
state. Previous work has suggested that the bang-bang structure of QAOA is
optimal but with significant caveats, leaving open the question of what
procedure is optimal in practice. In this work, we formalize the optimal control
arguments proving that a time-constrained procedure has a bang at the beginning
and end but can take on an annealing-like form in-between. In numerics on
transverse field Ising models, we show that bang-anneal-bang procedures are
common with optimal time-constrained QAOA Trotterizing the annealing portion.
We furthermore show an equivalence between different types of time-constraints
in this style of problem. The optimal procedures we find are far removed from a
monotonically changing adiabatic path in the short-time limit, but we show that
as the allowed time increases, the adiabatic limit and intuition from adiabatic
quantum computing apply.

**Tom Bannink, Jop Briët, Farrokh Labib and Hans Maassen. Quasirandom quantum channels**

**Abstract: **Mixing (or quasirandom) properties of the natural transition
matrix associated to a graph can be quantified by its distance to the complete
graph. Different mixing properties correspond to different norms to measure
this distance. For dense graphs, two such properties known as spectral
expansion and uniformity were shown to be equivalent in seminal 1989 work of
Chung, Graham and Wilson. Recently, Conlon and Zhao extended this equivalence
to the case of sparse vertex transitive graphs using the famous Grothendieck
inequality. Here we generalize these results to the non-commutative, or
‘quantum’, case, where a transition matrix becomes a quantum channel. In
particular, we show that for irreducibly covariant quantum channels, expansion
is equivalent to a natural analog of uniformity for graphs, generalizing the
result of Conlon and Zhao. Moreover, we show that in these results, the
non-commutative and commutative (resp.) Grothendieck inequalities yield the
best-possible constants.

**Tomotaka Kuwahara and ****Keiji Saito****. Strictly linear light cones in long-range interacting systems of arbitrary dimensions**

**Abstract: **In locally interacting quantum many-body systems, a velocity
of the information propagation is finitely bounded and the linear light cone
can be defined. Outside the light cone, amount of the information propagation
rapidly decays with the distance. When systems have long-range interactions, it
is highly nontrivial whether such a linear light cone exists or not. We herein
consider generic long-range interacting systems with decaying interactions as
$R^{-\alpha}$ with the distance $R$. We rigorously prove the existence of the
linear light cone for $\alpha>2D+1$ ($D$: the spatial dimension), where we
obtain the Lieb-Robinson bound as $\|[O_i(t),O_j]\| <
t^{2D+1}(R-\bar{v}t)^{-\alpha}$ with $\bar{v}=O(1)$ for arbitrary two operators
$O_i$ and $O_j$ separated by a distance $R$. Moreover, we give an explicit
quantum-state transfer protocol that achieves the above bound up to a constant
coefficient and violates the linear light cone for $\alpha<2D+1$. This
implies that our Lieb-Robinson bound is the best general upper bound in the
regime of $\alpha>2D+1$.

**Ivan Bardet, Angela Capel, Angelo Lucia, David Perez-Garcia and Cambyse Rouzé. On the modified logarithmic Sobolev inequality for the heat-bath dynamics for 1D systems**

**Abstract: **The mixing time of Markovian dissipative evolutions of open
quantum many-body systems can be bounded using optimal constants of certain
quantum functional inequalities, such as the modified logarithmic Sobolev
constant. For classical spin systems, the positivity of such constants follows
from a mixing condition for the Gibbs measure, via quasi-factorization results
for the entropy.

Inspired by the classical case, we present a strategy to derive the positivity
of the modified logarithmic Sobolev constant associated to the dynamics of
certain quantum systems from some clustering conditions on the Gibbs state of a
local, commuting Hamiltonian. In particular we show that for the heat-bath
dynamics for 1D systems, the modified logarithmic Sobolev constant is positive
under the assumptions of a mixing condition on the Gibbs state and a strong
quasi-factorization of the relative entropy.

**Anne Broadbent****, ****Sevag Gharibian**** and ****Hong-Sheng Zhou****. Towards Quantum One-Time Memories from Stateless Hardware**

**Abstract: **A central tenet of theoretical cryptography is the study of
the minimal assumptions required to implement a given cryptographic primitive.
One such primitive is the one-time memory (OTM), introduced by Goldwasser,
Kalai, and Rothblum [CRYPTO 2008], which is a classical functionality modeled
after a non-interactive 1-out-of-2 oblivious transfer, and which is complete
for one-time classical and quantum programs. It is known that secure OTMs do
not exist in the standard model in both the classical and quantum settings.
Here, we propose a scheme for using quantum information, together with the
assumption of stateless (i.e., reusable) hardware tokens, to build
statistically secure OTMs. Via the semidefinite programming-based quantum games
framework of Gutoski and Watrous [STOC 2007], we prove security for a malicious
receiver, against a linear number of adaptive queries to the token, in the
quantum universal composability framework, but leave open the question of security
against a polynomial amount of queries. Compared to alternative schemes derived
from the literature on quantum money, our scheme is technologically simple
since it is of the “prepare-and-measure” type. We also show our scheme is
“tight” according to two scenarios.

**Freek Witteveen, Michael Walter, Volkher Scholz and Brian Swingle. Quantum circuit approximations and entanglement renormalization for the Dirac field in 1+1 dimensions**

**Abstract: **The multiscale entanglement renormalization ansatz describes
quantum many-body states by a hierarchical entanglement structure organized by
length scale.

Numerically, it has been demonstrated to capture critical lattice models and
the data of the corresponding conformal field theories with high accuracy.

However, a rigorous understanding of its success and precise relation to the
continuum is still lacking.

To address this challenge, we provide an explicit construction of
entanglement-renormalization quantum circuits that rigorously approximate
correlation functions of the massless Dirac conformal field theory.

We directly target the continuum theory: discreteness is introduced by our
choice of how to probe the system, not by any underlying short-distance lattice
regulator.

To achieve this, we use multiresolution analysis from wavelet theory to obtain
an approximation scheme and to implement entanglement renormalization in a
natural way.

This could be a starting point for constructing quantum circuit approximations
for more general conformal field theories.

**Felix Leditzky****, Mohammad A. Alhejji, Joshua Levin and Graeme Smith. Playing Games with Multiple Access Channels**

**Abstract: **Communication networks have multiple users, each sending and
receiving messages. A multiple access channel (MAC) models multiple senders
transmitting to a single receiver, such as the uplink from many mobile phones
to a single base station. The optimal performance of a MAC is quantified by a
capacity region of simultaneously achievable communication rates. We study the
two-sender classical MAC, the simplest and best-understood network, and find a
surprising richness in both a classical and quantum context. First, we find
that quantum entanglement shared between senders can substantially boost the capacity
of a classical MAC. Second, we find that optimal performance of a MAC with
bounded-size inputs may require unbounded amounts of entanglement. Third,
determining whether a perfect communication rate is achievable using
finite-dimensional entanglement is undecidable. Finally, we show that
evaluating the capacity region of a two-sender classical MAC is in fact
NP-hard.

**Srijita Kundu, Jamie Sikora and Ernest Y.-Z. Tan. A device-independent protocol for XOR oblivious transfer**

**Abstract: **Oblivious transfer is a cryptographic primitive where Alice
has two bits and Bob wishes to learn some function of them. Ideally, Alice
should not learn Bob’s desired function choice and Bob should not learn any
more than logically implied by the function value. While decent quantum
protocols for this task are known, many quickly become insecure if an adversary
were to control the quantum devices used in the implementation of the protocol.
Here we present how some existing protocols fail in this device-independent
framework, and give a fully-device independent quantum protocol for XOR
oblivious transfer which is provably more secure than any classical protocol.

**Anurag Anshu, David Gosset and Karen Morenz. Slightly beyond product state approximations for a quantum analogue of Max Cut**

**Abstract: **We consider a computational problem where the goal is to
approximate the maximum eigenvalue of a two-local Hamiltonian that describes
antiferromagnetic Heisenberg interactions between qubits located at the
vertices of the graph. Previous work has shed light on this problem’s
approximability by \textit{product states}. For any instance of this problem
the maximum energy attained by a product state is lower bounded by the Max Cut
of the graph and upper bounded by the standard Goemans-Williamson semidefinite
programming relaxation of it. Gharibian and Parekh described an efficient
classical approximation algorithm for this problem which outputs a product
state with energy at least $0.498$ times the maximum eigenvalue in the worst
case, and observe that there exist instances where the best product state has
energy $1/2$ of optimal. We investigate approximation algorithms with
performance exceeding this limitation which are based on optimizing over tensor
products of few-qubit states and shallow quantum circuits. We provide an
efficient classical algorithm which achieves an approximation ratio of at least
$0.53$ in the worst case. We also show that for any instance defined by a $3$
or $4$-regular triangle-free graph, there is an efficiently computable shallow
quantum circuit that prepares a state with energy larger than the best product
state (larger even than its semidefinite programming relaxation).

### J**essica Bavaresco****, Mateus Araújo, Caslav Brukner and Marco Túlio Quintino. Semi-device-independent certification of indefinite causal order**

**Abstract: **When transforming pairs of independent quantum operations
according to the fundamental rules of quantum theory, an intriguing phenomenon
emerges: some such higher-order operations may act on the input operations in
an indefinite causal order. Recently, the formalism of process matrices has
been developed to investigate these noncausal properties of higher-order
operations. This formalism predicts, in principle, statistics that ensure
indefinite causal order even in a device-independent scenario, where the
involved operations are not characterised. Nevertheless, all physical
implementations of process matrices proposed so far require full characterisation
of the involved operations in order to certify such phenomena. Here we consider
a semi-device-independent scenario, which does not require all operations to be
characterised. We introduce a framework for certifying noncausal properties of
process matrices in this intermediate regime and use it to analyse the quantum
switch, a well-known higher-order operation, to show that, although it can only
lead to causal statistics in a device-independent scenario, it can exhibit
noncausal properties in semi-device-independent scenarios. This proves that the
quantum switch generates stronger noncausal correlations than it was previously
known.

**Daniel Stilck França****, Fernando G. S. L. Brandão and Richard Kueng. Faster quantum and classical SDP approximations for quadratic binary optimization**

**Abstract: **We give a quantum speedup for solving the canonical
semidefinite programming relaxation for binary quadratic optimization. The
class of relaxations for combinatorial optimization has so far eluded quantum
speedups. Our methods combine ideas from quantum Gibbs sampling and matrix
exponent updates. A de-quantization of the algorithm also leads to a faster
classical solver. For generic instances, our quantum solver gives a nearly
quadratic speedup over state-of-the-art algorithms. We also provide an
efficient randomized rounding procedure that converts approximately optimal SDP
solutions into constant factor approximations of the original quadratic
optimization problem.

**Xin Wang****. Optimizing the fundamental limits for quantum and private communication**

**Abstract: **The quantum capacity of a noisy quantum channel determines
the maximal rate at which we can code reliably over asymptotically many uses of
the channel, and it characterizes the channel’s ultimate ability to transmit
quantum information coherently. In this paper, we derive single-letter upper
bounds on the quantum and private capacities of quantum channels. The quantum
capacity of a quantum channel is always no larger than the quantum capacity of
its extended channels, since the extensions of the channel can be considered as
assistance from the environment. By optimizing the parametrized extended channels
with specific structures such as the flag structure, we obtain new upper bounds
on the quantum capacity of the original quantum channel. Furthermore, we extend
our approach to estimating the fundamental limits of private communication and
one-way entanglement distillation. As notable applications, we establish
improved upper bounds to the quantum and private capacities for fundamental
quantum channels of great interest in quantum information, some of which are
also the sources of noise in superconducting quantum computing. In particular,
our upper bounds on the quantum capacities of the depolarizing channel and the
generalized amplitude damping channel are strictly better than previously
best-known bounds.

**Ludovico Lami, Sumeet Khatri, ****Gerardo Adesso**** and ****Mark Wilde****. Extendibility of bosonic Gaussian states**

**Abstract: **xtendibility of bosonic Gaussian states is a key issue in
continuous-variable quantum information. We show that a bosonic Gaussian state
is $k$-extendible if and only if it has a Gaussian $k$-extension, and we derive
a simple semidefinite program, whose size scales linearly with the number of
local modes, to efficiently decide $k$-extendibility of any given bosonic
Gaussian state. When the system to be extended comprises one mode only, we
provide a closed-form solution. Implications of these results for the steerability
of quantum states and for the extendibility of bosonic Gaussian channels are
discussed. We then derive upper bounds on the distance of a $k$-extendible
bosonic Gaussian state to the set of all separable states, in terms of trace
norm and R\’enyi relative entropies. These bounds, which can be seen as
“Gaussian de Finetti theorems,” exhibit a universal scaling in the total
number of modes, independently of the mean energy of the state. Finally, we
establish an upper bound on the entanglement of formation of Gaussian
$k$-extendible states, which has no analogue in the finite-dimensional setting.

**Simon Becker, Nilanjana Datta, Ludovico Lami and Cambyse Rouzé. Convergence rates for the quantum central limit theorem**

**Abstract: **Various quantum analogues of the central limit theorem,
which is one of the cornerstones of probability theory, are known in the
literature. One such analogue, due to Cushen and Hudson, is of particular
relevance for quantum optics. It implies that the state in any single output
arm of an $n$-splitter, which is fed with $n$ copies of a centred state $\rho$
with finite second moments, converges to the Gaussian state with the same first
and second moments as $\rho$. Here we exploit the phase space formalism to
carry out a refined analysis of the rate of convergence in this quantum central
limit theorem. For instance, we prove that the convergence takes place at a
rate $\mathcal{O}\left(n^{-1/2}\right)$ in the Hilbert–Schmidt norm whenever
the third moments of $\rho$ are finite. Trace norm or relative entropy bounds
can be obtained by leveraging the energy boundedness of the state. Via
analytical and numerical examples we show that our results are tight in many
respects. An extension of our proof techniques to the non-i.i.d.\ setting is
used to analyse a new model of a lossy optical fibre, where a given $m$-mode
state enters a cascade of $n$ beam splitters of equal transmissivities
$\lambda^{1/n}$ fed with an arbitrary (but fixed) environment state. Assuming
that the latter has finite third moments, and ignoring unitaries, we show that
the effective channel converges in diamond norm to a simple thermal attenuator,
with a rate $\mathcal{O}\Big(n^{-\frac{1}{2(m+1)}}\Big)$. This allows us to
establish bounds on the classical and quantum capacities of the cascade
channel. Along the way, we derive several results that may be of independent
interest. For example, we prove that any quantum characteristic function
$\chi_\rho$ is uniformly bounded by some $\eta_\rho<1$ outside of any
neighbourhood of the origin; also, $\eta_\rho$ can be made to depend only on
the energy of the state $\rho$.

**Marco Fanizza, Matteo Rosati, Michalis Skotiniotis, ****John Calsamiglia**** and Vittorio Giovannetti. Beyond the swap test: efficient estimation of distances between quantum states**

**Abstract: **We study the problem of estimating distance measures between
unknown quantum states, given M and N copies of each type. For pure states, any
distance measure can be expressed in terms of the overlap between the states.
Overlap estimation is a fundamental primitive in quantum information processing
that is commonly accomplished from the outcomes of N swap-tests, a joint
measurement on one copy of each type whose outcome probability is a linear
function of the overlap. We show that a more precise estimate can be obtained
by allowing for general collective measurements on all copies, in particular
using weak Schur sampling. We derive the statistics of the optimal measurement
and compute the optimal mean square error in the asymptotic pointwise and
finite Bayesian estimation settings. Besides, we consider two strategies
relying on the estimation of one or both the states, and show that, although
they are suboptimal, they outperform the swap test. In particular, the swap
test is extremely inefficient for small values of the overlap, which become
exponentially more likely as the dimension increases.

We show that the optimal measurement is less invasive than the swap test and
study the robustness to depolarizing noise for qubit states.

In the case of mixed states, distance measure cannot be expressed in terms of a
single distance. With the swap test, one can estimate the Hilbert-Schmidt
distance and the overlap, but it is not possible to obtain other very relevant
distance measures. We show that simultaneous weak Schur sampling can instead
estimate the spectra of each of the states and of their convex combination,
with weight given by M/M+N and N/M+N. This estimate is much more informative
than the outcome of swap tests and it can be used to estimate a wider class of
properties and distinguishability measures. In particular we show how to
measure the Holevo quantity of a an ensemble constructed with the states. We
discuss how to get bounds on the trace distance using these estimates, and
apply these bounds to closeness and remoteness testing, improving sample
complexity with respect to the swap test.

**Aleksandrs Belovs**** and Ansis Rosmanis. Tight Quantum Lower Bound for Approximate Counting with Quantum States**

**Abstract: **We prove tight lower bounds for the following variant of the counting problem considered by Aaronson \etal.

The task is to distinguish whether an input set $x\subseteq [n]$ has size either $k$ or $k’=(1+\eps)k$.

We assume the algorithm has access to

\begin{itemize}

\item the membership oracle, which, for each $i\in [n]$, can answer whether $i\in x$, or not; and

\item the uniform superposition $\ket|\psi_x> = \sum_{i\in x} \ket|i>/\sqrt{|x|}$ over the elements of $x$.

Moreover, we consider three different ways how the algorithm can access this state:

\begin{itemize}

\item the algorithm can have copies of the state $\ket|\psi_x>$;

\item the algorithm can execute the reflecting oracle which reflects about the state $\ket|\psi_x>$;

\item the algorithm can execute the state-generating oracle (or its inverse) which performs the transformation $\ket|0>\mapsto\ket|\psi_x>$.

\end{itemize}

\end{itemize}

Without the second type of resources (related to $\ket|\psi_x>$), the problem is well-understood, see Brassard \etal.

The study of the problem with the second type of resources was recently initiated by Aaronson \etal.

We completely resolve the problem for all values of $1/k \le \eps\le 1$, giving tight trade-offs between all types of resources available to the algorithm.

Thus, we close the main open problems from Aaronson \etal.

The lower bounds are proven using variants of the adversary bound by Belovs and employing analysis closely related to the Johnson association scheme.

**Anirban Chowdhury, Rolando Somma and Yigit Subasi. Computing partition functions in the one clean qubit model**

**Abstract: **We present algorithms to evaluate partition functions of
quantum Hamiltonians using mixed-state quantum computation, specifically the
DQC1 model of computation which requires only one pure qubit. Our algorithm
provides an additive-error estimate to the normalized partition function in
time that is polynomial in the number of qubits, for a large class of Hamiltonians.
This implies that a variant of the partition function problem, that was
previously shown to be hard for the complexity class DQC1 by Brandao, is in
fact DQC1-complete. Our algorithm is based on approximations of the exponential
operator as linear combinations of unitaries, which are related to
block-encoding of Hamiltonians or Hamiltonian evolutions. We then extend our
results to give an algorithm that estimates the partition function within a
desired relative error. Towards this end, we develop a procedure based on a
sequence of approximations within predetermined additive errors that may be of
independent interest.

**Andreas Klingler, ****Gemma De Las Cuevas**** and Tim Netzer. Approximate tensor decompositions: disappearance of all separations**

**Abstract: **We study different decompositions of positive semidefinite matrices and nonnegative tensors and examine their approximate ranks. For any rank and norm, we define an epsilon rank as the minimum rank of an element which is epsilon close to the original element with respect to the given norm. We prove that the separations between these ranks disappear for a large class of Schatten p-norms and all entrywise p-norms with p > 1. For the trace norm (i.e. p = 1), we obtain a

dependence on the ambient dimension. Our main tool is an approximate version of Caratheodory’s Theorem. We also present a deterministic algorithm to find an approximate decomposition. This work implies that it must be possible to purify states approximately at a fixed cost, which shows that the positivity problem disappears in this case.

**Zvika Brakerski, Venkata Koppula, Umesh Vazirani and Thomas Vidick. Simpler Proofs of Quantumness**

**Abstract: **A proof of quantumness is a method for provably demonstrating (to a classical verifier) that a quantum device can perform computational tasks that a classical device with comparable resources cannot. Providing a proof of quantumness is the first step towards constructing a useful quantum computer.

There are currently three approaches for exhibiting proofs of quantumness: (i) Inverting a classically-hard one-way function (e.g.\ using Shor’s algorithm). This seems technologically out of reach. (ii) Sampling from a classically-hard-to-sample distribution (e.g.\ BosonSampling). This may be within reach of near-term experiments, but for all such tasks known verification requires exponential time. (iii) Interactive protocols based on cryptographic assumptions. The use of a trapdoor scheme allows for efficient verification, and implementation seems to require much less resources than (i), yet still more than (ii).

In this work we propose a significant simplification to approach (iii) by employing the random oracle heuristic. (We note that we do not apply the Fiat-Shamir paradigm.)

We give a two-message (challenge-response) proof of quantumness based on any trapdoor claw-free function. In contrast to earlier proposals we do not need an adaptive hard-core bit property. This allows the use of smaller security parameters and more diverse computational assumptions (such as Ring Learning with Errors), significantly reducing the quantum computational effort required for a successful demonstration.

**Marco Fanizza, Farzad Kianvash and Vittorio Giovannetti. Quantum flags, and new bounds on the quantum capacity of the depolarizing channel**

**Abstract: **A new bound for the quantum capacity of the d-dimensional
depolarizing channels is presented. Our derivation makes use of a flagged
extension of the map where the receiver obtains a copy of a state σ_0 whenever
the messages are transmitted without errors, and a copy of a state σ_1 when
instead the original state gets fully depolarized. By varying the overlap
between the flag states, the resulting transformation nicely interpolates
between the depolarizing map (when σ_0 = σ_1), and the d-dimensional erasure
channel (when σ_0 and σ_1 have orthogonal support). We find sufficient
conditions for degradability of the flagged channel, which let us to calculate
its quantum capacity in a suitable parameter region. From this last result we
get the upper bound for the depolarizing channel, which by a direct comparison
appears to be tighter than previous available results for d > 2, and for d =
2 it is tighter in an intermediate regime of noise. In particular, in the limit
of large d values, our findings presents a previously unnoticed O(1)
correction.

**Andris Ambainis and Nikita Larka. Quantum algorithms for computational geometry problems**

**Abstract: **We study quantum algorithms for problems in computational
geometry, such as Point-On-3-Lines problem. In this problem, we are given a set
of lines and we are asked to find a point that lies on at least 3 of these
lines. Point-On-3-Lines and many other computational geometry problems are
known to be 3Sum-Hard. That is, solving them classically requires time
\Omega(n^{2-o(1)}), unless there is faster algorithm for the well known 3Sum
problem (in which we are given a set S of n integers and have to determine if
there are a, b, c \in S such that a + b + c = 0).

Quantumly, 3Sum can be solved in time O(n log n) using Grover’s quantum search
algorithm. This leads to a question: can we solve Point-On-3-Lines and other
3Sum-Hard problems in O(n^c) time quantumly, for c<2?

We answer this question affirmatively, by constructing a quantum algorithm that
solves Point-On-3-Lines in time O(n^{1 + o(1)}). The algorithm combines
recursive use of amplitude amplification with geometrical ideas. We show that
the same ideas give O(n^{1 + o(1)}) time algorithm for many 3Sum-Hard
geometrical problems.

**Srinivasan Arunachalam****, ****Aleksandrs Belovs****, ****Andrew Childs****, ****Robin Kothari****, Ansis Rosmanis and ****Ronald de Wolf****. Quantum Coupon Collector**

**Abstract: **We study how efficiently a k-element set S subseteq [n] can
be learned from a uniform superposition ket{S} of its elements.

One can think of ket{S}=sum_{i in S} ket{i}/sqrt{|S|} as the quantum version of
a uniformly random sample over S, as in the classical analysis of the
“coupon collector problem.” We show that if k is close to n, then we
can learn S using asymptotically fewer quantum samples than random samples. In
particular, if there are n-k=O(1) missing elements then O(k) copies of ket{S}
suffice, in contrast to the Theta(k log k) random samples needed by a classical
coupon collector. On the other hand, if n-k=Omega(k), then Omega(k log k)
quantum samples are necessary.

More generally, we give tight bounds on the number of quantum samples needed
for every k and n, and we give efficient quantum learning algorithms. We also
give tight bounds in the model where we can additionally reflect through
ket{S}. Finally, we relate coupon collection to a known example separating
proper and improper PAC learning that turns out to show no separation in the
quantum case.

**Das Poulami, Christopher Pattison, Srilatha Manne, Doug Carmean, Krysta Svore, Moinuddin Qureshi and Nicolas Delfosse. A Scalable Decoder Micro-architecture for Fault-Tolerant Quantum Computing**

**Abstract: **Quantum computation promises significant computational
advantages over classical computation for some problems. However, quantum
hardware suffers from much higher error rates than in classical hardware. As a
result, extensive quantum error correction is required to execute a useful
quantum algorithm. The decoder is a key component of the error correction
scheme whose role is to identify errors faster than they accumulate in the
quantum computer and that must be implemented with minimum hardware resources
in order to scale to the regime of practical applications. In this work, we
consider surface code error correction, which is the most popular family of
error correcting codes for quantum computing, and we design a decoder
micro-architecture for the Union-Find decoding algorithm. We propose a
three-stage fully pipelined hardware implementation of the decoder that
significantly speeds up the decoder. Then, we optimize the amount of decoding
hardware required to perform error correction simultaneously over all the
logical qubits of the quantum computer. By sharing resources between logical
qubits, we obtain a 67% reduction of the number of hardware units and the
memory capacity is reduced by 70%. Moreover, we reduce the bandwidth required
for the decoding process by a factor at least 30x using low-overhead
compression algorithms. Finally, we provide numerical evidence that our
optimized micro-architecture can be executed fast enough to correct errors in a
quantum computer.

**Scott Aaronson, Nai-Hui Chia, Han-Hsuan Lin, Chunhao Wang and Ruizhe Zhang. On Quantum Complexity for Closest Pair and Orthogonal Vectors**

**Abstract: **The closest pair problem is a fundamental problem of
computational geometry: given a set of $n$ points in a $d$-dimensional space,
find a pair with the smallest distance. A classical algorithm taught in
introductory courses solves this problem in $O(n\log n)$ time in constant
dimensions (i.e., when $d=O(1)$). This paper asks and answers the question of
the problem’s quantum {time} complexity. Specifically, we give an
$\tilde{O}(n^{2/3})$ algorithm in constant dimensions, which is optimal up to a
polylogarithmic factor by the lower bound on the quantum query complexity of
element distinctness. The key to our algorithm is an efficient
history-independent data structure that supports quantum interference.

In $\polylog(n)$ dimensions, no known quantum algorithms perform better than
brute force search, with a quadratic speedup provided by Grover’s algorithm. To
give evidence that the quadratic speedup is nearly optimal, we initiate the
study of quantum fine-grained complexity and introduce the \emph{Quantum Strong
Exponential Time Hypothesis (QSETH)}, which is based on the assumption that
Grover’s algorithm is optimal for \textsf{CNF-SAT} when the clause width is
large. We show that the na\”{i}ve Grover approach to closest pair in
higher dimensions is optimal up to an $n^{o(1)}$ factor unless QSETH is false.
We also study the bichromatic closest pair problem and the orthogonal vectors
problem, with broadly similar results.

**Niel De Beaudrap, Xiaoning Bian and Quanlong Wang. Fast and effective techniques for T-count reduction via spider nest identities**

**Abstract: **In fault-tolerant quantum computing systems, realising
(approximately) universal quantum computation is usually described in terms of
realising Clifford+T operations, which is to say a circuit of CNOT, Hadamard,
and pi/2-phase rotations, together with T operations (pi/4-phase rotations).
For many error correcting codes, fault-tolerant realisations of Clifford
operations are significantly less resource-intensive than those of T gates,
which motivates finding ways to realise the same transformation involving
T-count (the number of T gates involved) which is as low as possible.
Investigations into this problem has led to observations that this problem is
closely related to NP-hard tensor decomposition problems and is tantamount to
the difficult problem of decoding exponentially long Reed-Muller codes. This
problem then presents itself as one for which must be content in practise with
approximate optimisation, in which one develops an array of tactics to be
deployed through some pragmatic strategy. In this vein, we describe techniques
to reduce the T-count, based on the effective application of “spider nest
identities”: easily recognised products of parity-phase operations which
are equivalent to the identity operation. We demonstrate the effectiveness of
such techniques by obtaining improvements in the T-counts of a number of
circuits, in run-times which are typically less than the time required to make
a fresh cup of coffee.

**Hamoon Mousavi, Seyed Sajjad Nezhadi and ****Henry Yuen****. On the complexity of zero gap MIP***

**Abstract: **The class MIP^* is the set of languages that are decidable
by a multiprover interactive proof with quantum entangled provers. It was
recently shown by Ji, Natarajan, Vidick, Wright and Yuen that MIP^* is equal to
RE, the set of recursively enumerable languages. In particular this showed that
the complexity of approximating the quantum value of a non-local game G is, in
general, equivalent to the complexity of the Halting problem.

In this paper we investigate the complexity of deciding whether the quantum
value of a non-local game G is 1. This problem corresponds to a complexity class
that we call zero gap MIP^*, denoted by MIP^*_0, where there is no promise gap
between the verifier’s acceptance probabilities in the YES and NO cases. We
prove that MIP^*_0 extends beyond the first level of the arithmetical hierarchy
(which includes RE and its complement coRE), and in fact is equal to PI^0_2,
the class of languages that can be decided by quantified formulas of the form
for all y, there exists z, R(x,y,z).

Combined with the previously known result that MIP^co_0, the commuting operator
variant of MIP^*_0, is equal to coRE, our result further highlights the
fascinating connection between various models of quantum multiprover
interactive proofs and different classes in computability theory.

**James R. Seddon, ****Bartosz Regula****, Hakop Pashayan, Yingkai Ouyang and ****Earl T. Campbell****. Quantifying quantum speedups: improved classical simulation from tighter magic monotones**

**Abstract: **In the stabilizer circuit model of quantum computation,
universality requires a resource known as magic. Here, we propose three new
ways to quantify the magic of a quantum state using magic monotones, apply the
monotones in the characterization of state conversions under stabilizer operations,
and connect them with the classical simulation of quantum circuits. We first
present a complete theory of these quantifiers for tensor products of
single-qubit states, for which the monotones are all equal and all act
multiplicatively, constituting the first qubit magic monotones to have this
property. We use the monotones to establish several asymptotic and
non-asymptotic bounds on state interconversion and distillation rates. We then
relate our quantifiers directly to the runtime of classical simulation
algorithms, showing that a large amount of magic is a necessary requirement for
any quantum speedup. One of our classical simulation algorithms is a
quasi-probability simulator with its runtime connected to a generalized notion
of negativity, which is exponentially faster than all prior qubit
quasi-probability simulation algorithms. We also introduce a new variant of the
stabilizer rank simulation algorithm suitable for mixed states, while improving
the runtime bounds for this class of simulations. Our work reveals interesting
connections between quasi-probability and stabilizer rank simulators, which
previously appeared to be unrelated. Generalizing the approach beyond the
theory of magic states, we establish methods for the quantitative characterization
of classical simulability for more general quantum resources, and use them in
the resource theory of quantum coherence to connect the L1-norm of coherence
with the simulation of free operations.

**Nicholas Hunter-Jones, Richard Kueng, Wissam Chemissany, Fernando Brandao and John Preskill. Models of quantum complexity growth**

**Abstract: **The concept of quantum complexity has far-reaching
implications spanning theoretical computer science, quantum many-body physics,
and high energy physics. The quantum complexity of a unitary transformation or
quantum state is defined as the size of the shortest quantum computation that
executes the unitary or prepares the state. It is reasonable to expect that the
complexity of a quantum state governed by a chaotic many-body Hamiltonian grows
linearly with time for a time that is exponential in the system size; however,
because it is hard to rule out a short-cut that improves the efficiency of a
computation, it is notoriously difficult to derive lower bounds on quantum
complexity for particular unitaries or states without making additional
assumptions. To go further, one may study more generic models of complexity
growth. We provide a rigorous connection between complexity growth and unitary
k-designs, ensembles which capture the randomness of the unitary group. This
connection allows us to leverage existing results about design growth to draw
conclusions about the growth of complexity. We prove that local random quantum
circuits generate unitary transformations whose complexity grows linearly for a
long time, mirroring the behavior one expects in chaotic quantum systems and
verifying conjectures by Brown and Susskind. Moreover, our results apply under
a strong definition of quantum complexity based on optimal distinguishing measurements.

**Nicholas Hunter-Jones. Unitary designs from statistical mechanics in random quantum circuits**

**Abstract: **Random quantum circuits are proficient information
scramblers and efficient generators of randomness, rapidly approximating
moments of the unitary group. We study the convergence of local random quantum
circuits to unitary k-designs. Employing a statistical mechanical mapping, we
give an exact expression of the distance to forming an approximate design as a
lattice partition function. In the statistical mechanics model, the approach to
randomness has a simple interpretation in terms of domain walls extending
through the circuit. We analytically compute the second moment, showing that
random circuits acting on n qudits form approximate 2-designs in O(n) depth, as
is known. Furthermore, we argue that random circuits form approximate unitary
k-designs in O(nk) depth and are thus essentially optimal in both n and k. We
can show this in the limit of large local dimension, but more generally rely on
a conjecture about the dominance of certain domain wall configurations.

**Jonas Haferkamp, Felipe Montealegre-Mora, Markus Heinrich, Jens Eisert, David Gross and Ingo Roth. Efficient unitary designs with a system size independent number of non-Clifford gates**

**Abstract: **Many quantum information protocols require the
implementation of random unitaries. Because it takes exponential resources to
produce Haar-random unitaries drawn from the full n-qubit group, one often
resorts to t-designs. Unitary t-designs mimic Haar-randomness up to t-th
moments. It is known that Clifford operations can implement at most unitary
3-designs. In this work, we quantify the non-Clifford resources required to
break this barrier.

Exploiting a recently developed variant of Schur-Weyl duality for the Clifford
group, wefind that it suffices to inject $O(t^4*\log^2(t),
\log(1/\varepsilon))$ non-Clifford gates into a polynomial depth random
Clifford circuit to obtain an ε-approximate t-design. Strikingly, the number n
of qubits does not enter – asymptotically, the density of non-Clifford gates is
allowed to tend to zero.

As an auxiliary result that might be of independent interest, we obtain
explicit bounds on the convergence time of random Clifford circuits to the t-th
moment of the

uniform distribution on the Clifford group.

**Harry Buhrman****, Subhasree Patro and Florian Speelman. A Framework of Quantum Strong Exponential-Time Hypotheses**

**Abstract: **The strong exponential-time hypothesis (SETH) is a commonly used conjecture in the field of complexity theory. It states that CNF formulas cannot be analyzed for satisfiability with a speedup over exhaustive search. This hypothesis and its variants gave rise to a fruitful field of research, fine-grained complexity, obtaining (mostly tight) lower bounds for many problems in P whose unconditional lower bounds are hard to find. In this work, we introduce a framework of Quantum Strong Exponential-Time Hypotheses, as quantum analogues to SETH.

Using the QSETH framework, we are able to translate quantum query lower bounds on black-box problems to conditional quantum time lower bounds for many problems in BQP. As an example, we illustrate the use of the QSETH by providing a conditional quantum time lower bound of $\Omega(n^{1.5})$ for the Longest Common Subsequence and Edit Distance problems. We also show that the $n^2$ SETH-based lower bound for a recent scheme for Proofs of Useful Work, based on the Orthogonal Vectors problem, holds for quantum computation assuming QSETH, maintaining a quadratic gap between verifier and prover.

**Arkin Tikku, ****Mario Berta**** and ****Joseph M. Renes****. Non-additivity in classical-quantum wiretap channels**

**Abstract: **Due to Csiszar and Koerner, the capacity of classical
wiretap channels has a single-letter characterization in terms of the private
information. For quantum wiretap channels, however, it is known that
regularization of the private information is necessary to reach the capacity.
Here, we study hybrid classical-quantum wiretap channels in order to resolve to
what extent quantum effects are needed to witness non-additivity phenomena in
quantum Shannon theory. For wiretap channels with quantum inputs but classical
outputs, we prove that the characterization of the capacity in terms of the
private information stays single-letter. Hence, entangled input states are of
no asymptotic advantage in this setting. For wiretap channels with classical
inputs, we show by means of explicit examples that the private information
already becomes non-additive when either one of the two receivers becomes
quantum (with the other receiver staying classical). This gives non-additivity
examples that are not caused by entanglement and illustrates that quantum
adversaries are strictly different from classical adversaries in the wiretap
model.