NDLI: Testing Product States, Quantum Merlin-Arthur Games and Tensor Optimization

Content Provider	ACM Digital Library
Author	Harrow, Aram W Montanaro, Ashley
Copyright Year	2013
Abstract	We give a test that can distinguish efficiently between product states of $\textit{n}$ quantum systems and states that are far from product. If applied to a state $\|\textit{ψ}〉$ whose maximum overlap with a product state is 1 ™ $\textit{ε},$ the test passes with probability 1 ™ $\textit{Θ}(\textit{ε}),$ regardless of $\textit{n}$ or the local dimensions of the individual systems. The test uses two copies of $\|\textit{ψ}〉.$ We prove correctness of this test as a special case of a more general result regarding stability of maximum output purity of the depolarizing channel. A key application of the test is to quantum Merlin-Arthur games with multiple Merlins, where we obtain several structural results that had been previously conjectured, including the fact that efficient soundness amplification is possible and that two Merlins can simulate many Merlins: $QMA(\textit{k})$ = QMA(2) for $\textit{k}$ ≥ 2. Building on a previous result of Aaronson et al., this implies that there is an efficient quantum algorithm to verify 3-SAT with constant soundness, given two unentangled proofs of $\textit{Õ}(√\textit{n})$ qubits. We also show how QMA(2) with log-sized proofs is equivalent to a large number of problems, some related to quantum information (such as testing separability of mixed states) as well as problems without any apparent connection to quantum mechanics (such as computing injective tensor norms of 3-index tensors). As a consequence, we obtain many hardness-of-approximation results, as well as potential algorithmic applications of methods for approximating QMA(2) acceptance probabilities. Finally, our test can also be used to construct an efficient test for determining whether a unitary operator is a tensor product, which is a generalization of classical linearity testing.
Starting Page	1
Ending Page	43
Page Count	43
File Format	PDF
ISSN	00045411
e-ISSN	1557735X
DOI	10.1145/2432622.2432625
Journal	Journal of the ACM (JACM)
Volume Number	60
Issue Number	1
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2013-02-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Entanglement Quantum Merlin-Arthur games Tensor optimization
Content Type	Text
Resource Type	Article
Subject	Hardware and Architecture Information Systems Control and Systems Engineering Artificial Intelligence Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Space-bounded probabilistic game automata

Finite state verifiers I: the power of interaction

Finite state verifiers II: zero knowledge

An Efficient Test for Product States with Applications to Quantum Merlin-Arthur Games

Testing product states, quantum Merlin-Arthur games and tensor optimisation

Computing with highly mixed states

Limits on the ability of quantum states to convey classical messages

Efficient Planarity Testing

Generalized Quantum Arthur-Merlin Games

Testing Product States, Quantum Merlin-Arthur Games and Tensor Optimization

Similar Documents

Space-bounded probabilistic game automata

Finite state verifiers I: the power of interaction

Finite state verifiers II: zero knowledge

An Efficient Test for Product States with Applications to Quantum Merlin-Arthur Games

Testing product states, quantum Merlin-Arthur games and tensor optimisation

Computing with highly mixed states

Limits on the ability of quantum states to convey classical messages

Efficient Planarity Testing

Generalized Quantum Arthur-Merlin Games

Testing Product States, Quantum Merlin-Arthur Games and Tensor Optimization