Alex May

Non-local quantum computation (NLQC) replaces a local interaction between two systems with a single round of communication and shared entanglement. Despite many partial results, it is known that a characterization of entanglement cost in at least certain NLQC tasks would imply significant breakthroughs in complexity theory. Here, we avoid these obstructions and take an indirect approach to understanding resource requirements in NLQC, which mimics the approach used by complexity theorists: we study the relative hardness of different NLQC tasks by identifying resource efficient reductions between them. Most significantly, we prove that f -measure and f -route, the two best studied NLQC tasks, are in fact equivalent under O ( 1 ) overhead reductions. This result simplifies many existing proofs in the literature and extends several new properties to f -measure. For instance, we obtain sub-exponential upper bounds on f -measure for all functions, and efficient protocols for functions in the complexity class M o d k L . Beyond this, we study a number of other examples of NLQC tasks and their relationships.

The conditional disclosure of secrets (CDS) setting is among the most basic primitives studied in information-theoretic cryptography. Motivated by a connection to non-local quantum computation and position-based cryptography, CDS with quantum resources has recently been considered. Here, we study the differences between quantum and classical CDS, with the aims of clarifying the power of quantum resources in information-theoretic cryptography. We establish the following results:1) We prove a Ω ( log ⁡ R 0 , A → B ( f ) + log ⁡ R 0 , B → A ( f ) ) lower bound on quantum CDS where R 0 , A → B ( f ) is the classical one-way communication complexity with perfect correctness.2) We prove a lower bound on quantum CDS in terms of two round, public coin, two-prover interactive proofs.3) For perfectly correct CDS, we give a separation for a promise version of the not-equals function, showing a quantum upper bound of O ( log ⁡ n ) and classical lower bound of Ω ( n ) .4) We give a logarithmic upper bound for quantum CDS on forrelation, while the best known classical algorithm is linear. We interpret this as preliminary evidence that classical and quantum CDS are separated even with correctness and security error allowed.We also give a separation for classical and quantum private simultaneous message passing for a partial function, improving on an earlier relational separation. Our results use novel combinations of techniques from non-local quantum computation and communication complexity.

In an entanglement summoning task, a set of distributed, co-operating parties attempt to fulfill requests to prepare entanglement between distant locations. The parties share limited communication resources: timing constraints may require the entangled state be prepared before some pairs of distant parties can communicate, and a restricted set of links in a quantum network may further constrain communication. Building on earlier work, we continue the characterization of entanglement summoning. We give an if and only if condition on entanglement summoning tasks with only bidirected causal connections, and provide a set of sufficient conditions addressing the most general case containing both oriented and bidirected causal connections. Our results rely on the recent development of entanglement sharing schemes.

Determining and verifying an object's position is a fundamental task with broad practical relevance. We propose a secure quantum ranging protocol that combines quantum ranging with quantum position verification (QPV). Our method achieves Heisenberg-limited precision in position estimation while simultaneously detecting potential cheaters. Two verifiers each send out a state that is entangled in frequency space within a single optical mode. An honest prover only needs to perform simple beam-splitter operations, whereas cheaters are allowed to use arbitrary linear optical operations, one ancillary mode, and perfect quantum memories-though without access to entanglement. Our approach considers a previously unstudied security aspect to quantum ranging. It also provides a framework to quantify the precision with which a prover's position can be verified in QPV, which previously has been assumed to be infinite. We further discuss the near-term experimental implementation of our scheme and propose how a better-than-classical advantage can be observed using existing photonic technologies.