cs.CC

# Title:An approximation algorithm for approximation rank

Abstract: One of the strongest techniques available for showing lower bounds on quantum communication complexity is the logarithm of the approximation rank of the communication matrix--the minimum rank of a matrix which is entrywise close to the communication matrix. This technique has two main drawbacks: it is difficult to compute, and it is not known to lower bound quantum communication complexity with entanglement.
Linial and Shraibman recently introduced a norm, called gamma_2^{alpha}, to quantum communication complexity, showing that it can be used to lower bound communication with entanglement. Here the parameter alpha is a measure of approximation which is related to the allowable error probability of the protocol. This bound can be written as a semidefinite program and gives bounds at least as large as many techniques in the literature, although it is smaller than the corresponding alpha-approximation rank, rk_alpha. We show that in fact log gamma_2^{alpha}(A)$and log rk_{alpha}(A)$ agree up to small factors. As corollaries we obtain a constant factor polynomial time approximation algorithm to the logarithm of approximate rank, and that the logarithm of approximation rank is a lower bound for quantum communication complexity with entanglement.
 Comments: 9 pages Subjects: Computational Complexity (cs.CC) Cite as: arXiv:0809.2093 [cs.CC] (or arXiv:0809.2093v1 [cs.CC] for this version)

## Submission history

From: Troy Lee [view email]
[v1] Thu, 11 Sep 2008 20:06:56 UTC (9 KB)
{"ft_lang_label":"__label__en","ft_lang_prob":0.89011467,"math_prob":0.8153951,"size":1570,"snap":"2019-26-2019-30","text_gpt3_token_len":324,"char_repetition_ratio":0.14878672,"word_repetition_ratio":0.008810572,"special_character_ratio":0.19745223,"punctuation_ratio":0.08745247,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9763865,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2019-07-18T05:32:59Z\",\"WARC-Record-ID\":\"<urn:uuid:22c9a473-5767-4f12-a491-5820e63d3e3a>\",\"Content-Length\":\"18756\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:68c268da-dade-4cd5-99f0-8dbbd5b11d27>\",\"WARC-Concurrent-To\":\"<urn:uuid:8fe04f55-095a-4246-b74e-765d0ad6f706>\",\"WARC-IP-Address\":\"128.84.21.199\",\"WARC-Target-URI\":\"https://arxiv.org/abs/0809.2093v1\",\"WARC-Payload-Digest\":\"sha1:3IRFSNVGEFZIIQYNJNP6YFR7NRFXEKJL\",\"WARC-Block-Digest\":\"sha1:UPFZHTTNI3PTONOWIMKDKZVMIPLFXKKG\",\"WARC-Identified-Payload-Type\":\"application/xhtml+xml\",\"warc_filename\":\"/cc_download/warc_2019/CC-MAIN-2019-30/CC-MAIN-2019-30_segments_1563195525500.21_warc_CC-MAIN-20190718042531-20190718064531-00302.warc.gz\"}"}