BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Matthias Christandl

Matthias Christandl contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
quant-phComputational Complexitymath-phmath.ACmath.COmath.MPmath.GR

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
11works
0followers
7topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

11 published item(s)

preprint2026arXiv

Making Existing Quantum Position Verification Protocols Secure Against Arbitrary Transmission Loss

Signal loss poses a significant threat to the security of quantum cryptography when the chosen protocol lacks loss-tolerance. In quantum position verification (QPV) protocols, even relatively small loss rates can compromise security. The goal is thus to find protocols that remain secure under practically achievable loss rates. In this work, we modify the usual structure of QPV protocols and prove that this modification makes the potentially high transmission loss between the verifiers and the prover security-irrelevant for a class of protocols that includes a practically-interesting candidate protocol inspired by the BB84 protocol ($\mathrm{QPV}_{\mathrm{BB84}}^{f}$). This modification, which involves photon presence detection, a small time delay at the prover, and a commitment to play before proceeding, reduces the overall loss rate to just the prover's laboratory. The adapted protocol c-$\mathrm{QPV}_{\mathrm{BB84}}^{f}$ then becomes a practically feasible QPV protocol with strong security guarantees, even against attackers using adaptive strategies. As the loss rate between the verifiers and prover is mainly dictated by the distance between them, secure QPV over longer distances becomes possible. We also show possible implementations of the required photon presence detection, making c-$\mathrm{QPV}_{\mathrm{BB84}}^{f}$ a protocol that solves all major practical issues in QPV. Finally, we discuss experimental aspects and give parameter estimations.

0 citations0 reviewsNo code linkedOpen access
preprint2024arXiv

Tip of the Quantum Entropy Cone

Relations among von Neumann entropies of different parts of an $N$-partite quantum system have direct impact on our understanding of diverse situations ranging from spin systems to quantum coding theory and black holes. Best formulated in terms of the set $Σ^*_N$ of possible vectors comprising the entropies of the whole and its parts, the famous strong subaddivity inequality constrains its closure $\overlineΣ^*_N$, which is a convex cone. Further homogeneous constrained inequalities are also known. In this work we provide (non-homogeneous) inequalities that constrain $Σ_N^*$ near the apex (the vector of zero entropies) of $\overlineΣ^*_N$, in particular showing that $Σ_N^*$ is not a cone for $N\geq 3$. Our inequalities apply to vectors with certain entropy constraints saturated and, in particular, they show that while it is always possible to up-scale an entropy vector to arbitrary integer multiples it is not always possible to down-scale it to arbitrarily small size, thus answering a question posed by A. Winter. Relations of our work to topological materials, entanglement theory, and quantum cryptography are discussed.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

An Operational Environment for Quantum Self-Testing

Observed quantum correlations are known to determine in certain cases the underlying quantum state and measurements. This phenomenon is known as (quantum) self-testing. Self-testing constitutes a significant research area with practical and theoretical ramifications for quantum information theory. But since its conception two decades ago by Mayers and Yao, the common way to rigorously formulate self-testing has been in terms of operator-algebraic identities, and this formulation lacks an operational interpretation. In particular, it is unclear how to formulate self-testing in other physical theories, in formulations of quantum theory not referring to operator-algebra, or in scenarios causally different from the standard one. In this paper, we explain how to understand quantum self-testing operationally, in terms of causally structured dilations of the input-output channel encoding the correlations. These dilations model side-information which leaks to an environment according to a specific schedule, and we show how self-testing concerns the relative strength between such scheduled leaks of information. As such, the title of our paper has double meaning: we recast conventional quantum self-testing in terms of information-leaks to an environment -- and this realises quantum self-testing as a special case within the surroundings of a general operational framework. Our new approach to quantum self-testing not only supplies an operational understanding apt for various generalisations, but also resolves some unexplained aspects of the existing definition, naturally suggests a distance measure suitable for robust self-testing, and points towards self-testing as a modular concept in a larger, cryptographic perspective.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Barriers for fast matrix multiplication from irreversibility

Determining the asymptotic algebraic complexity of matrix multiplication, succinctly represented by the matrix multiplication exponent $ω$, is a central problem in algebraic complexity theory. The best upper bounds on $ω$, leading to the state-of-the-art $ω\leq 2.37..$, have been obtained via the laser method of Strassen and its generalization by Coppersmith and Winograd. Recent barrier results show limitations for these and related approaches to improve the upper bound on $ω$. We introduce a new and more general barrier, providing stronger limitations than in previous work. Concretely, we introduce the notion of "irreversibility" of a tensor and we prove (in some precise sense) that any approach that uses an irreversible tensor in an intermediate step (e.g., as a starting tensor in the laser method) cannot give $ω= 2$. In quantitative terms, we prove that the best upper bound achievable is lower bounded by two times the irreversibility of the intermediate tensor. The quantum functionals and Strassen support functionals give (so far, the best) lower bounds on irreversibility. We provide lower bounds on the irreversibility of key intermediate tensors, including the small and big Coppersmith--Winograd tensors, that improve limitations shown in previous work. Finally, we discuss barriers on the group-theoretic approach in terms of "monomial" irreversibility.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Symmetric Subrank of Tensors and Applications

Strassen (Strassen, J. Reine Angew. Math., 375/376, 1987) introduced the subrank of a tensor as a natural extension of matrix rank to tensors. Subrank measures the largest diagonal tensor that can be obtained by applying linear operations to the different indices (legs) of the tensor (just like the matrix rank measures the largest diagonal matrix that can be obtained using row and column operations). Motivated by problems in combinatorics and complexity theory we introduce the new notion of symmetric subrank of tensors by restricting these linear operations to be the same for each index. We prove precise relations and separations between subrank and symmetric subrank. We prove that for symmetric tensors the subrank and the symmetric subrank are asymptotically equal. This proves the asymptotic subrank analogon of a conjecture known as Comon's conjecture in the theory of tensors. This result allows us to prove a strong connection between the general and symmetric version of an asymptotic duality theorem of Strassen. We introduce a representation-theoretic method to asymptotically bound the symmetric subrank called the symmetric quantum functional in analogy with the quantum functionals (Christandl, Vrana, Zuiddam, J. Amer. Math. Soc., 2021), and we study the relations between these functionals.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Larger Corner-Free Sets from Combinatorial Degenerations

There is a large and important collection of Ramsey-type combinatorial problems, closely related to central problems in complexity theory, that can be formulated in terms of the asymptotic growth of the size of the maximum independent sets in powers of a fixed small (directed or undirected) hypergraph, also called the Shannon capacity. An important instance of this is the corner problem studied in the context of multiparty communication complexity in the Number On the Forehead (NOF) model. Versions of this problem and the NOF connection have seen much interest (and progress) in recent works of Linial, Pitassi and Shraibman (ITCS 2019) and Linial and Shraibman (CCC 2021). We introduce and study a general algebraic method for lower bounding the Shannon capacity of directed hypergraphs via combinatorial degenerations, a combinatorial kind of "approximation" of subgraphs that originates from the study of matrix multiplication in algebraic complexity theory (and which play an important role there) but which we use in a novel way. Using the combinatorial degeneration method, we make progress on the corner problem by explicitly constructing a corner-free subset in $F_2^n \times F_2^n$ of size $Ω(3.39^n/poly(n))$, which improves the previous lower bound $Ω(2.82^n)$ of Linial, Pitassi and Shraibman (ITCS 2019) and which gets us closer to the best upper bound $4^{n - o(n)}$. Our new construction of corner-free sets implies an improved NOF protocol for the Eval problem. In the Eval problem over a group $G$, three players need to determine whether their inputs $x_1, x_2, x_3 \in G$ sum to zero. We find that the NOF communication complexity of the Eval problem over $F_2^n$ is at most $0.24n + O(\log n)$, which improves the previous upper bound $0.5n + O(\log n)$.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Noise-robust exploration of many-body quantum states on near-term quantum devices

We describe a resource-efficient approach to studying many-body quantum states on noisy, intermediate-scale quantum devices. We employ a sequential generation model that allows us to bound the range of correlations in the resulting many-body quantum states. From this, we characterize situations where the estimation of local observables does not require the preparation of the entire state. Instead smaller patches of the state can be generated from which the observables can be estimated. This can potentially reduce circuit size and number of qubits for the computation of physical properties of the states. Moreover, we show that the effect of noise decreases along the computation. Our results apply to a broad class of widely studied tensor network states and can be directly applied to near-term implementations of variational quantum algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Quantum Circuits for Isometries

We consider the decomposition of arbitrary isometries into a sequence of single-qubit and Controlled-NOT (C-NOT) gates. In many experimental architectures, the C-NOT gate is relatively 'expensive' and hence we aim to keep the number of these as low as possible. We derive a theoretical lower bound on the number of C-NOT gates required to decompose an arbitrary isometry from m to n qubits, and give three explicit gate decompositions that achieve this bound up to a factor of about two in the leading order. We also perform some bespoke optimizations for certain cases where m and n are small. In addition, we show how to apply our result for isometries to give decomposition schemes for arbitrary quantum operations and POVMs via Stinespring's theorem. These results will have an impact on experimental efforts to build a quantum computer, enabling them to go further with the same resources.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Asymptotic performance of port-based teleportation

Quantum teleportation is one of the fundamental building blocks of quantum Shannon theory. While ordinary teleportation is simple and efficient, port-based teleportation (PBT) enables applications such as universal programmable quantum processors, instantaneous non-local quantum computation and attacks on position-based quantum cryptography. In this work, we determine the fundamental limit on the performance of PBT: for arbitrary fixed input dimension and a large number $N$ of ports, the error of the optimal protocol is proportional to the inverse square of $N$. We prove this by deriving an achievability bound, obtained by relating the corresponding optimization problem to the lowest Dirichlet eigenvalue of the Laplacian on the ordered simplex. We also give an improved converse bound of matching order in the number of ports. In addition, we determine the leading-order asymptotics of PBT variants defined in terms of maximally entangled resource states. The proofs of these results rely on connecting recently-derived representation-theoretic formulas to random matrix theory. Along the way, we refine a convergence result for the fluctuations of the Schur-Weyl distribution by Johansson, which might be of independent interest.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Highly Entangled States With Almost No Secrecy

In this paper we illuminate the relation between entanglement and secrecy by providing the first example of a quantum state that is highly entangled, but from which, nevertheless, almost no secrecy can be extracted. More precisely, we provide two bounds on the bipartite entanglement of the totally antisymmetric state in dimension d x d. First, we show that the amount of secrecy that can be extracted from the state is low, to be precise it is bounded by O(1/d). Second, we show that the state is highly entangled in the sense that we need a large amount of singlets to create the state: entanglement cost is larger than a constant, independent of d. In order to obtain our results we use representation theory, linear programming and the entanglement measure known as squashed entanglement. Our findings also clarify the relation between the squashed entanglement and the relative entropy of entanglement.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Even Partitions in Plethysms

We prove that for all natural numbers k,n,d with k <= d and every partition lambda of size kn with at most k parts there exists an irreducible GL(d, C)-representation of highest weight 2*lambda in the plethysm Sym^k(Sym^(2n) (C^d)). This gives an affirmative answer to a conjecture by Weintraub (J. Algebra, 129 (1):103-114, 1990). Our investigation is motivated by questions of geometric complexity theory and uses ideas from quantum information theory.

0 citations0 reviewsNo code linkedOpen access