Author name cluster

Falk Unger

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

1 author row

FOCS Conference 2014 Conference Paper

Noisy Interactive Quantum Communication

Gilles Brassard
Ashwin Nayak 0001
Alain Tapp
Dave Touchette
Falk Unger

We study the problem of simulating protocols in a quantum communication setting over noisy channels. This problem falls at the intersection of quantum information theory and quantum communication complexity, and will be of importance for eventual real-world applications of interactive quantum protocols, which can be proved to have exponentially lower communication costs than their classical counterparts for some problems. These are the first results concerning the quantum version of this problem, originally studied by Schulman in a classical setting (FOCS '92, STOC '93). We simulate a length N quantum communication protocol by a length O(N) protocol with arbitrarily small error. Our simulation strategy has a far higher communication rate than a naive one that encodes separately each particular round of communication to achieve comparable success. Such a strategy would have a communication rate going to 0 in the worst interaction case as the length of the protocols increases, in contrast to our strategy, which has a communication rate proportional to the capacity of the channel used. Under adversarial noise, our strategy can withstand, for arbitrarily small ε > 0, error rates as high as 1/2 -- ε when parties preshare perfect entanglement, but the classical channel is noisy. We show that this is optimal. Note that in this model, the naive strategy would not work for any constant fraction of errors. We provide extension of these results in several other models of communication, including when also the entanglement is noisy, and when there is no pre-shared entanglement but communication is quantum and noisy. We also study the case of random noise, for which we provide simulation protocols with positive communication rates and no pre-shared entanglement over some quantum channels with quantum capacity Q = 0, proving that Q is in general not the right characterization of a channel's capacity for interactive quantum communication. Our results are stated for a general quantum communication protocol in which Alice and Bob collaborate, and hold in particular in the quantum communication complexity settings of the Yao and Cleve-Buhrman models.

Details

FOCS Conference 2009 Conference Paper

A Probabilistic Inequality with Applications to Threshold Direct-Product Theorems

Falk Unger

We prove a simple concentration inequality, which is an extension of the Chernoff bound and Hoeffding's inequality for binary random variables. Instead of assuming independence of the variables we use a slightly weaker condition, namely bounds on the co-moments. This inequality allows us to simplify and strengthen several known direct-product theorems and establish new threshold direct-product theorems. Threshold direct-product theorems are statements of the following form: If one instance of a problem can be solved with probability at most p, then solving significantly more than a p-fraction among multiple instances has negligible probability. Results of this kind are crucial when distinguishing whether a process succeeds with probability s or c, for 0 < s < c < 1. Here standard direct-product theorems are of no help since even a process which can solve one instance with probability c will only be able to solve all k instances with exponentially small probability. Using our concentration inequality we show how to obtain threshold (and standard) direct-product theorems from known XOR Lemmas. We give examples of this approach and obtain (threshold) direct-product theorems for quantum XOR games, quantum random access codes, 2-party and multi-party communication complexity and circuits. Similar results can be obtained for other models of computation, e. g. polynomials over GF(2). It is well-known that direct-product theorems and XOR Lemmas are "essentially" equivalent. We show that one direction is often even tight: going from XOR Lemmas to (threshold) direct-product theorems is possible in an information-theoretically optimal way. We believe that our inequality has applications in other contexts as well.

Details

FOCS Conference 2006 Conference Paper

New Limits on Fault-Tolerant Quantum Computation

Harry Buhrman
Richard Cleve
Monique Laurent
Noah Linden
Alexander Schrijver
Falk Unger

We show that quantum circuits cannot be made fault-tolerant against a depolarizing noise level of thetas = (6 - 2radic2)/7 ap 45%, thereby improving on a previous bound of 50% (due to Razborov, 2004). More precisely, the circuit model for which we prove this bound contains perfect gates from the Clifford group (CNOT, Hadamard, S, X, Y, Z) and arbitrary additional one-qubit gates that are subject to depolarizing noise thetas. We prove that this set of gates cannot be universal for arbitrary (even classical) computation, from which the upper bound on the noise threshold for fault-tolerant quantum computation follows

Details

MFCS Conference 2005 Conference Paper

On Small Hard Leaf Languages

Falk Unger

Abstract This paper deals with balanced leaf language complexity classes, introduced independently in [1] and [14]. We propose the seed concept for leaf languages, which allows us to give “short” representations for leaf words. We then use seeds to show that leaf languages A with NP ⊆ BLeaf P ( A ) cannot be polylog-sparse (i. e. census A ∈ O (log O (1) )), unless PH collapses. We also generalize balanced ≤ \(^{P, {bit}}_{m}\) -reductions, which were introduced in [6], to other bit-reductions, for example (balanced) truth-table- and Turing-bit-reductions. Then, similarly to above, we prove that NP and Σ \(^{P}_{\rm 2}\) cannot have polylog-sparse hard sets under those balanced truth-table- and Turing-bit-reductions, if the polynomial-time hierarchy is infinite.

Details