检索结果-内蒙古大学图书馆

Optimality of the pretty good measurement for port-based teleportation

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Leditzky, Felix Department of Mathematics IQUIST University of Illinois Urbana-Champaign Institute for Quantum Computing Department of Combinatorics and Optimization University of Waterloo Perimeter Institute for Theoretical Physics Canada

Port-based teleportation (PBT) is a protocol in which Alice teleports an unknown quantum state to Bob using measurements on a shared entangled multipartite state called the port state and forward classical communication. In this paper, we give an explicit proof that the so-called pretty good measurement, or square-root measurement, is optimal for the PBT protocol with independent copies of maximally entangled states as the port state. We then show that the very same measurement remains optimal even when the port state is optimized to yield the best possible PBT protocol. Hence, there is one particular pretty good measurement achieving the optimal performance in both cases. The following well-known facts are key ingredients in the proofs of these results: (i) the natural symmetries of PBT, leading to a description in terms of representation-theoretic data;(ii) the operational equivalence of PBT with certain state discrimination problems, which allows us to employ duality of the associated semidefinite programs. Along the way, we rederive the representation-theoretic formulas for the performance of PBT protocols proved in [Studzinski et al., 2017] and [Mozrzymas et al., 2018] using only standard techniques from the representation theory of the unitary and symmetric groups. Providing a simplified derivation of these beautiful formulas is one of the main goals of this paper. Copyright © 2020, The Authors. All rights reserved.

关键词：

Erasable bit commitment from temporary quantum trust

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Lütkenhaus, Norbert Marwah, Ashutosh S. Touchette, Dave Institute for Quantum Computing Department of Physics and Astronomy University of Waterloo Perimeter Institute for Theoretical Physics Institute for Quantum Computing Department of Combinatorics and Optimization University of Waterloo Departement d'informatique Institut Quantique Universite de Sherbrooke

We introduce a new setting for two-party cryptography with temporarily trusted third parties. In addition to Alice and Bob in this setting, there are additional third parties, which Alice and Bob both trust to be honest during the protocol. However, once the protocol concludes, there is no guarantee over the behaviour of these third parties. It is possible that they collaborate and act adversarially. Our goal is to use these third parties to facilitate protocols which are impossible in two-party cryptography. We implement a variant of bit commitment in this setting, which we call erasable bit commitment. In this primitive, Alice has the choice of either opening or erasing her commitment after the commit phase. The ability to ask for an erasure allows Alice to ask the trusted parties to erase her commitment in case the trust period is about to expire. This erasure prevents a future coalition of the third parties and Bob from extracting any information about the commitment. However, this ability also makes erasable bit commitment weaker than the standard version of bit commitment. In addition to satisfying the security requirements of bit commitment, our protocol also does not reveal any information about the commitment to the third parties. Lastly, our protocol for this primitive requires a constant number of trusted third parties and can tolerate a small number of corrupt trusted parties as well as implementation errors. Copyright © 2019, The Authors. All rights reserved.

关键词： Cryptography

A compressed classical description of quantum states

学校读者我要写书评

暂无评论

arXiv 2018年

作者： Gosset, David Smolin, John Ibm T.J. Watson Research Center United States Department of Combinatorics and Optimization Institute for Quantum Computing University of Waterloo Canada

We show how to approximately represent a quantum state using the square root of the usual amount of classical memory. The classical representation of an n-qubit state ψ consists of its inner products with O(√2n) stabilizer states. A quantum state initially specified by its 2nentries in the computational basis can be compressed to this form in time O(2npoly(n)), and, subsequently, the compressed description can be used to additively approximate the expectation value of an arbitrary observable. Our compression scheme directly gives a new protocol for the vector in subspace problem with randomized one-way communication complexity that matches (up to polylogarithmic factors) the optimal upper bound, due to Raz. We obtain an exponential improvement over Raz's protocol in terms of computational efficiency. Copyright © 2018, The Authors. All rights reserved.

关键词： Computational efficiency

Device-independent uncloneable encryption

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Kundu, Srijita Tan, Ernest Y.-Z. Institute for Quantum Computing Department of Combinatorics and Optimization University of Waterloo WaterlooONN2L 3G1 Canada

Uncloneable encryption, first introduced by Broadbent and Lord (TQC 2020) is a quantum encryption scheme in which a quantum ciphertext cannot be distributed between two non-communicating parties such that, given access to the decryption key, both parties cannot learn the underlying plaintext. In this work, we introduce a variant of uncloneable encryption in which several possible decryption keys can decrypt a particular encryption, and the security requirement is that two parties who receive independently generated decryption keys cannot both learn the underlying ciphertext. We show that this variant of uncloneable encryption can be achieved device-independently, i.e., without trusting the quantum states and measurements used in the scheme, and that this variant works just as well as the original definition in constructing quantum money. Moreover, we show that a simple modification of our scheme yields a single-decryptor encryption scheme, which was a related notion introduced by Georgiou and Zhandry. In particular, the resulting single-decryptor encryption scheme achieves device-independent security with respect to a standard definition of security against random plaintexts. Finally, we derive an "extractor" result for a two-adversary scenario, which in particular yields a single-decryptor encryption scheme for single bit-messages that achieves perfect anti-piracy security without needing the quantum random oracle model. © 2022, CC BY.

关键词： Ciphertext

Estimating the Cost of Generic quantum Pre-image Attacks on SHA-2 and SHA-3 23rd

学校读者我要写书评

暂无评论

Estimating the Cost of Generic Quantum Pre-image Attacks on ...

23rd International Conference on Selected Areas in Cryptography, SAC 2016

作者： Amy, Matthew Di Matteo, Olivia Gheorghiu, Vlad Mosca, Michele Parent, Alex Schanck, John David R. Cheriton School of Computer Science University of Waterloo Waterloo Canada Department of Physics and Astronomy University of Waterloo Waterloo Canada Department of Combinatorics and Optimization University of Waterloo Waterloo Canada Institute for Quantum Computing University of Waterloo Waterloo Canada Perimeter Institute for Theoretical Physics Waterloo Canada Canadian Institute for Advanced Research Toronto Canada

ISBN: (纸本)9783319694528

We investigate the cost of Grover’s quantum search algorithm when used in the context of pre-image attacks on the SHA-2 and SHA-3 families of hash functions. Our cost model assumes that the attack is run on a surface code based fault-tolerant quantum computer. Our estimates rely on a time-area metric that costs the number of logical qubits times the depth of the circuit in units of surface code cycles. As a surface code cycle involves a significant classical processing stage, our cost estimates allow for crude, but direct, comparisons of classical and quantum algorithms. We exhibit a circuit for a pre-image attack on SHA-256 that is approximately 2153.8 surface code cycles deep and requires approximately 2.12.6 logical qubits. This yields an overall cost of 2.166.4 logical-qubit-cycles. Likewise we exhibit a SHA3-256 circuit that is approximately 2.146.5 surface code cycles deep and requires approximately 2.20 logical qubits for a total cost of, again, 2.166.5logical-qubit-cycles. Both attacks require on the order of 2128 queries in a quantum black-box model, hence our results suggest that executing these attacks may be as much as 275 billion times more expensive than one would expect from the simple query analysis. © 2017, Springer International Publishing AG.

关键词： Hash functions

Rate-Distortion Theory for Mixed States

学校读者我要写书评

暂无评论

Rate-Distortion Theory for Mixed States

2023 IEEE International Symposium on Information Theory, ISIT 2023

作者： Khanian, Zahra Baghali Kuroiwa, Kohdai Leung, Debbie Technical University of Munich Munich Center for Quantum Science and Technology Zentrum Mathematik Garching85748 Germany Institute for Quantum Computing University of Waterloo ONN2L 3G1 Canada University of Waterloo Department of Combinatorics and Optimization Canada Perimeter Institute for Theoretical Physics ONN2L 2Y5 Canada

ISBN: (纸本)9781665475549

In this paper we consider the compression of asymptotically many i.i.d. copies of ensembles of mixed quantum states where the encoder has access to a side information system. This source is equivalently defined as a classical-quantum state, namely, a quantum system correlated with a classical system playing the role of an inaccessible reference system. The figure of merit is evaluated based on per-copy or local error criterion. The rate-distortion theory aims to reveal the trade-off between the compression rate and the per-copy error. The optimal trade-off can be characterized by the rate-distortion function, which is the best rate given a certain distortion. In this paper, we analyze the rate-distortion functions of mixed-state compression. We find the rate-distortion functions in the entanglement-assisted and unassisted scenarios, in terms of a single-letter mutual information quantity and the regularized entanglement of purification, respectively. © 2023 IEEE.

关键词： Signal distortion

From communication complexity to an entanglement spread area law in the ground state of gapped local Hamiltonians

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Anshu, Anurag Harrow, Aram W. Soleimanifar, Mehdi Institute for Quantum Computing Department of Combinatorics and Optimization University of Waterloo Canada Perimeter Institute for Theoretical Physics Canada Center for Theoretical Physics MIT United States

In this work, we make a connection between two seemingly different problems. The first problem involves characterizing the properties of entanglement in the ground state of gapped local Hamiltonians, which is a central topic in quantum many-body physics. The second problem is on the quantum communication complexity of testing bipartite states with EPR assistance, a well-known question in quantum information theory. We construct a communication protocol for testing (or measuring) the ground state and use its communication complexity to reveal a new structural property for the ground state entanglement. This property, known as the entanglement spread, roughly measures the log of the ratio between the largest and the smallest Schmidt coefficients across a bipartite cut in the ground state. Our main result shows that gapped ground states possess limited entanglement spread across any cut, exhibiting an "area law" behavior. Our result quite generally applies to any interaction graph with an improved bound for the special case of lattices. This entanglement spread area law includes interaction graphs constructed in [AHL+14] that violate a generalized area law for the entanglement entropy. Our construction also provides evidence for a conjecture in physics by Li and Haldane on the entanglement spectrum of lattice Hamiltonians [LH08]. On the technical side, we use recent advances in Hamiltonian simulation algorithms along with the quantum phase estimation to give a new construction for an approximate ground space projector (AGSP) over arbitrary interaction graphs, which might be of independent interest. Copyright © 2020, The Authors. All rights reserved.

关键词： Ground state

Entanglement subvolume law for 2D frustration-free spin systems

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Anshu, Anurag Arad, Itai Gosset, David Institute for Quantum Computing University of Waterloo Canada Department of Combinatorics and Optimization University of Waterloo Canada Perimeter Institute for Theoretical Physics Canada Physics Department Technion Israel

Let H be a frustration-free Hamiltonian describing a 2D grid of qudits with local interactions, a unique ground state, and local spectral gap lower bounded by a positive constant. For any bipartition defined by a vertical cut of length L running from top to bottom of the grid, we prove that the corresponding entanglement entropy of the ground state of H is upper bounded by Õ(L5/3). For the special case of a 1D chain, our result provides a new area law which improves upon prior work, in terms of the scaling with qudit dimension and spectral gap. In addition, for any bipartition of the grid into a rectangular region A and its complement, we show that the entanglement entropy is upper bounded as Õ(|∂A|5/3) where ∂A is the boundary of A. This represents the first subvolume bound on entanglement in frustration-free 2D systems. In contrast with previous work, our bounds depend on the local (rather than global) spectral gap of the Hamiltonian. We prove our results using a known method which bounds the entanglement entropy of the ground state in terms of certain properties of an approximate ground state projector (AGSP). To this end, we construct a new AGSP which is based on a robust polynomial approximation of the AND function and we show that it achieves an improved trade-off between approximation error and entanglement. Copyright © 2019, The Authors. All rights reserved.

关键词： Ground state

quantum State Preparation with Optimal T-Count

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Gosset, David Kothari, Robin Wu, Kewen Google Quantum AI United States Department of Combinatorics and Optimization Institute for Quantum Computing University of Waterloo Canada Perimeter Institute for Theoretical Physics Canada University of California Berkeley United States

How many T gates are needed to approximate an arbitrary n-qubit quantum state to within error Ε? Improving prior work of Low, Kliuchnikov, and Schaeffer, we show that the optimal asymptotic scaling is Θ (Formula Presented) if we allow ancilla qubits. We also show that this is the optimal T -count for implementing an arbitrary diagonal n-qubit unitary to within error Ε. We describe applications in which a tensor product of many single-qubit unitaries can be synthesized in parallel for the price of one. Copyright © 2024, The Authors. All rights reserved.

关键词： Qubits