Bounds on Instantaneous Nonlocal Quantum Computation. Gonzales, A. & Chitambar, E. IEEE Transactions on Information Theory, 66(5):2951-2963, IEEE, 5, 2020. ![Bounds on Instantaneous Nonlocal Quantum Computation [pdf]](https://bibbase.org/img/filetypes/pdf.svg "pdf")
Paper ![Bounds on Instantaneous Nonlocal Quantum Computation [link]](https://bibbase.org/img/filetypes/link.svg "link")
Website doi abstract bibtex 9 downloads Instantaneous nonlocal quantum computation refers to a process in which spacelike separated parties simulate a nonlocal quantum operation on their joint systems through the consumption of pre-shared entanglement. To prevent a violation of causality, this simulation succeeds up to local errors that can only be corrected after the parties communicate classically with one another. However, this communication is non-interactive, and it involves just the broadcasting of local measurement outcomes. We refer to this operational paradigm as local operations and broadcast communication (LOBC) to distinguish it from the standard local operations and (interactive) classical communication (LOCC). In this paper, we show that an arbitrary two-quibt gate can be implemented by LOBC with $\epsilon$-error using $O(\log(1/\epsilon))$ entangled bits (ebits). This offers an exponential improvement over the best known two-qubit protocols, whose ebit costs behave as $O(1/\epsilon)$. We also consider the family of binary controlled gates on dimensions $d_A\otimes d_B$. We find that any hermitian gate of this form can be implemented by LOBC using a single shared ebit. In sharp contrast, a lower bound of $\log d_B$ ebits is shown in the case of generic (i.e. non-hermitian) gates from this family, even when $d_A=2$. This demonstrates an unbounded entanglement cost between LOCC and LOBC gate implementation. Furthermore, whereas previous lower bounds on the entanglement cost for instantaneous nonlocal computation restrict the minimum dimension of the needed entanglement, we bound its entanglement entropy. To our knowledge this is the first such lower bound of its kind.
@article{
title = {Bounds on Instantaneous Nonlocal Quantum Computation},
type = {article},
year = {2020},
pages = {2951-2963},
volume = {66},
websites = {https://ieeexplore.ieee.org/document/8886512/},
month = {5},
publisher = {IEEE},
id = {2c4f493d-97a4-32e2-880a-3276ca5a6a51},
created = {2020-04-26T04:46:42.935Z},
file_attached = {true},
profile_id = {5ed10b2c-e6b8-3ad8-bec0-45bb1010ca06},
last_modified = {2020-09-12T18:42:40.158Z},
read = {true},
starred = {false},
authored = {true},
confirmed = {true},
hidden = {false},
private_publication = {false},
abstract = {Instantaneous nonlocal quantum computation refers to a process in which spacelike separated parties simulate a nonlocal quantum operation on their joint systems through the consumption of pre-shared entanglement. To prevent a violation of causality, this simulation succeeds up to local errors that can only be corrected after the parties communicate classically with one another. However, this communication is non-interactive, and it involves just the broadcasting of local measurement outcomes. We refer to this operational paradigm as local operations and broadcast communication (LOBC) to distinguish it from the standard local operations and (interactive) classical communication (LOCC). In this paper, we show that an arbitrary two-quibt gate can be implemented by LOBC with $\epsilon$-error using $O(\log(1/\epsilon))$ entangled bits (ebits). This offers an exponential improvement over the best known two-qubit protocols, whose ebit costs behave as $O(1/\epsilon)$. We also consider the family of binary controlled gates on dimensions $d_A\otimes d_B$. We find that any hermitian gate of this form can be implemented by LOBC using a single shared ebit. In sharp contrast, a lower bound of $\log d_B$ ebits is shown in the case of generic (i.e. non-hermitian) gates from this family, even when $d_A=2$. This demonstrates an unbounded entanglement cost between LOCC and LOBC gate implementation. Furthermore, whereas previous lower bounds on the entanglement cost for instantaneous nonlocal computation restrict the minimum dimension of the needed entanglement, we bound its entanglement entropy. To our knowledge this is the first such lower bound of its kind.},
bibtype = {article},
author = {Gonzales, Alvin and Chitambar, Eric},
doi = {10.1109/TIT.2019.2950190},
journal = {IEEE Transactions on Information Theory},
number = {5}
}
Downloads: 9
{"_id":"voSuCwTCfGBp8qn57","bibbaseid":"gonzales-chitambar-boundsoninstantaneousnonlocalquantumcomputation-2020","authorIDs":["PqnfcCTDh2C7T9Fs7","W7YG7gy5PpzLKPAwc","h7zdz6e3hSdGiNbGz","o2ejS6RYLpGPuopad","pombtjmJLe3eqeuMN"],"author_short":["Gonzales, A.","Chitambar, E."],"bibdata":{"title":"Bounds on Instantaneous Nonlocal Quantum Computation","type":"article","year":"2020","pages":"2951-2963","volume":"66","websites":"https://ieeexplore.ieee.org/document/8886512/","month":"5","publisher":"IEEE","id":"2c4f493d-97a4-32e2-880a-3276ca5a6a51","created":"2020-04-26T04:46:42.935Z","file_attached":"true","profile_id":"5ed10b2c-e6b8-3ad8-bec0-45bb1010ca06","last_modified":"2020-09-12T18:42:40.158Z","read":"true","starred":false,"authored":"true","confirmed":"true","hidden":false,"private_publication":false,"abstract":"Instantaneous nonlocal quantum computation refers to a process in which spacelike separated parties simulate a nonlocal quantum operation on their joint systems through the consumption of pre-shared entanglement. To prevent a violation of causality, this simulation succeeds up to local errors that can only be corrected after the parties communicate classically with one another. However, this communication is non-interactive, and it involves just the broadcasting of local measurement outcomes. We refer to this operational paradigm as local operations and broadcast communication (LOBC) to distinguish it from the standard local operations and (interactive) classical communication (LOCC). In this paper, we show that an arbitrary two-quibt gate can be implemented by LOBC with $\\epsilon$-error using $O(\\log(1/\\epsilon))$ entangled bits (ebits). This offers an exponential improvement over the best known two-qubit protocols, whose ebit costs behave as $O(1/\\epsilon)$. We also consider the family of binary controlled gates on dimensions $d_A\\otimes d_B$. We find that any hermitian gate of this form can be implemented by LOBC using a single shared ebit. In sharp contrast, a lower bound of $\\log d_B$ ebits is shown in the case of generic (i.e. non-hermitian) gates from this family, even when $d_A=2$. This demonstrates an unbounded entanglement cost between LOCC and LOBC gate implementation. Furthermore, whereas previous lower bounds on the entanglement cost for instantaneous nonlocal computation restrict the minimum dimension of the needed entanglement, we bound its entanglement entropy. To our knowledge this is the first such lower bound of its kind.","bibtype":"article","author":"Gonzales, Alvin and Chitambar, Eric","doi":"10.1109/TIT.2019.2950190","journal":"IEEE Transactions on Information Theory","number":"5","bibtex":"@article{\n title = {Bounds on Instantaneous Nonlocal Quantum Computation},\n type = {article},\n year = {2020},\n pages = {2951-2963},\n volume = {66},\n websites = {https://ieeexplore.ieee.org/document/8886512/},\n month = {5},\n publisher = {IEEE},\n id = {2c4f493d-97a4-32e2-880a-3276ca5a6a51},\n created = {2020-04-26T04:46:42.935Z},\n file_attached = {true},\n profile_id = {5ed10b2c-e6b8-3ad8-bec0-45bb1010ca06},\n last_modified = {2020-09-12T18:42:40.158Z},\n read = {true},\n starred = {false},\n authored = {true},\n confirmed = {true},\n hidden = {false},\n private_publication = {false},\n abstract = {Instantaneous nonlocal quantum computation refers to a process in which spacelike separated parties simulate a nonlocal quantum operation on their joint systems through the consumption of pre-shared entanglement. To prevent a violation of causality, this simulation succeeds up to local errors that can only be corrected after the parties communicate classically with one another. However, this communication is non-interactive, and it involves just the broadcasting of local measurement outcomes. We refer to this operational paradigm as local operations and broadcast communication (LOBC) to distinguish it from the standard local operations and (interactive) classical communication (LOCC). In this paper, we show that an arbitrary two-quibt gate can be implemented by LOBC with $\\epsilon$-error using $O(\\log(1/\\epsilon))$ entangled bits (ebits). This offers an exponential improvement over the best known two-qubit protocols, whose ebit costs behave as $O(1/\\epsilon)$. We also consider the family of binary controlled gates on dimensions $d_A\\otimes d_B$. We find that any hermitian gate of this form can be implemented by LOBC using a single shared ebit. In sharp contrast, a lower bound of $\\log d_B$ ebits is shown in the case of generic (i.e. non-hermitian) gates from this family, even when $d_A=2$. This demonstrates an unbounded entanglement cost between LOCC and LOBC gate implementation. Furthermore, whereas previous lower bounds on the entanglement cost for instantaneous nonlocal computation restrict the minimum dimension of the needed entanglement, we bound its entanglement entropy. To our knowledge this is the first such lower bound of its kind.},\n bibtype = {article},\n author = {Gonzales, Alvin and Chitambar, Eric},\n doi = {10.1109/TIT.2019.2950190},\n journal = {IEEE Transactions on Information Theory},\n number = {5}\n}","author_short":["Gonzales, A.","Chitambar, E."],"urls":{"Paper":"https://bibbase.org/service/mendeley/5ed10b2c-e6b8-3ad8-bec0-45bb1010ca06/file/0280c368-7337-02eb-466f-f7f4538b01be/Gonzales_Chitambar___2019___Bounds_on_Instantaneous_Nonlocal_Quantum_Computation.pdf.pdf","Website":"https://ieeexplore.ieee.org/document/8886512/"},"biburl":"https://bibbase.org/service/mendeley/5ed10b2c-e6b8-3ad8-bec0-45bb1010ca06","bibbaseid":"gonzales-chitambar-boundsoninstantaneousnonlocalquantumcomputation-2020","role":"author","metadata":{"authorlinks":{"chitambar, e":"https://quantum-entangled.ece.illinois.edu/publications/"}},"downloads":9},"bibtype":"article","creationDate":"2020-06-01T20:55:41.968Z","downloads":9,"keywords":[],"search_terms":["bounds","instantaneous","nonlocal","quantum","computation","gonzales","chitambar"],"title":"Bounds on Instantaneous Nonlocal Quantum Computation","year":2020,"biburl":"https://bibbase.org/service/mendeley/5ed10b2c-e6b8-3ad8-bec0-45bb1010ca06","dataSources":["9eser9nRTJ8sJHJ3r","ya2CyA73rpZseyrZ8","2252seNhipfTmjEBQ"]}