Decidability of fully quantum nonlocal games with noisy maximally entangled states
Abstract
This paper considers the decidability of fully quantum nonlocal games with noisy maximally entangled states. Fully quantum nonlocal games are a generalization of nonlocal games, where both questions and answers are quantum and the referee performs a binary POVM measurement to decide whether they win the game after receiving the quantum answers from the players. The quantum value of a fully quantum nonlocal game is the supremum of the probability that they win the game, where the supremum is taken over all the possible entangled states shared between the players and all the valid quantum operations performed by the players. The seminal work [23, 24] implies that it is undecidable to approximate the quantum value of a fully nonlocal game. This still holds even if the players are only allowed to share (arbitrarily many copies of) maximally entangled states. This paper investigates the case that the shared maximally entangled states are noisy. We prove that there is a computable upper bound on the copies of noisy maximally entangled states for the players to win a fully quantum nonlocal game with a probability arbitrarily close to the quantum value. This implies that it is decidable to approximate the quantum values of these games. Hence, the hardness of approximating the quantum value of a fully quantum nonlocal game is not robust against the noise in the shared states.
This paper is built on the framework for the decidability of non-interactive simulations of joint distributions [17, 12, 16] and generalizes the analogous result for nonlocal games in [36]. We extend the theory of Fourier analysis to the space of super-operators and prove several key results including an invariance principle and a dimension reduction for super-operators. These results are interesting in their own right and are believed to have further applications.
1 Introduction
Nonlocal games are a core model in the theory of quantum computing, which has found wide applications in quantum complexity theory, quantum cryptography, and the foundation of quantum mechanics. A nonlocal game is executed by three parties, a referee and two non-communicating players, which are usually named Alice and Bob. Before the game starts, the players may share an arbitrary bipartite quantum state. The referee samples a pair of questions and sends each of them to the players, separately. Each player is supposed to reply with a classical answer to the referee. They win the game if the questions and the answers satisfy a given predicate. The distribution of the questions and the predicate is known to the players. The quantum value is the supremum of the probability that the players win the game. It is a central topic in quantum computing to understand the computational complexity of computing the quantum value of a nonlocal game. After decades of efforts [11, 28, 27, 21, 22, 33, 14], it has been finally settled by the seminal work [23, 24], where Ji, Natarajan, Vidick, Wright and Yuen proved that it is undecidable to approximately compute the quantum value of a nonlocal game with constant precision. This result implies that there is no computable upper bound on the preshared entanglement for the players to win the game with a probability close to the quantum value. Otherwise, the probability of success can be obtained by -netting all possible quantum strategies and brute-force searching for the optimal value. Ji et al. essentially proved that it is still uncomputable even if the players are only allowed to share (arbitrarily many) EPR states.
In [36], the authors investigated the robustness of the hardness of the nonlocal games under noise. More specifically, they considered a variant of nonlocal games, where the preshared quantum states are corrupted. It is shown that the quantum value of a nonlocal game is computable if the players are allowed to share arbitrarily many copies of noisy maximally entangled states (MES). Hence, the hardness of the nonlocal games collapses in the presence of noise from the preshared entangled states.
In this paper, we consider fully quantum nonlocal games, which are a broader class of games where both questions and answers are quantum and the predicates are replaced by quantum measurements with binary outcomes: win and loss. More specifically, a fully quantum nonlocal game
consists of a referee and two non-communicating players: Alice and Bob, where are quantum systems, is a tripartite quantum state in and is a measurement acting on . Alice, Bob, and the referee share the input state , where Alice, Bob, and the referee hold , respectively, at the beginning of the game. Alice and Bob are supposed to perform quantum operations mapping to and to , and then send the quantum states in and to the referee, respectively. After receiving the quantum messages from the players, the referee performs the POVM measurement . Again, the players are allowed to share arbitrary quantum states before the game starts. Both players know the description of and the POVM. The quantum value of the game is the supremum of the probability that the players win the game. The supremum is over all possible preshared quantum states and the quantum operations that can be implemented by both parties. It is not hard to see if and both and are projectors on computational basis, where is a bipartite distribution, then it boils down to a nonlocal game.
Fully quantum nonlocal games also capture the complexity class of two-prover one-round quantum multi-prover interactive proof systems . The variants of nonlocal games, where either the questions or the answers are replaced by quantum messages have occurred in much literature [7, 30, 37, 10, 15, 8, 5, 25]. In [7], Buscemi introduced the so-called semi-quantum nonlocal games, which are nonlocal games with quantum questions and classical answers, and proved that semi-quantum nonlocal games can be used to characterize LOSR (local operations and shared randomness) paradigm. Such games are further used to study the entanglement verification in the subsequent work [8, 5]. In a different context, Regev and Vidick in [37] proposed quantum XOR games, where the questions are quantum and the answers are still classical. In [30], Leung, Toner, and Watrous introduced a communication task: coherent state exchange and its analogue in the setting of nonlocal games, where both questions and answers are quantum. In [15], Fitzsimons and Vidick demonstrated an efficient reduction that transforms a local Hamiltonian into a 5-players nonlocal game allowing classical questions and quantum answers. They showed that approximating the value of this game to a polynomial inverse accuracy is -complete. In [10], Chung, Wu, and Yuen further proved a parallel repetition for nonlocal games where again questions are classical and answers are quantum.
As fully quantum nonlocal games are a generalization of nonlocal games, Ji et al.’s result [23, 24] implies that it is also undecidable to approximately compute the quantum value of a fully quantum nonlocal game, even if they are only allowed to share MESs.
In this paper, we continue the line of research in [36] to investigate whether the hardness of fully quantum nonlocal games can be maintained against the noise. More specifically, we consider the games where the players share arbitrarily many copies of noisy MES’s . Each is a bipartite state in quantum system , where Alice and Bob hold and , respectively. The value of a game can be written as
where the maximum is taken over all quantum operations and . Noisy MESs were introduced in [36], which will be defined later. They include depolarized EPR states , where and is an EPR state. [23, 24] proved that it is undecidable to approximate within constant precision.
Main results
In this paper, we prove that it is computable to approximate within arbitrarily small precision if is a noisy MES.
Theorem 1.1 (Main result, informal).
Given integer , and a fully quantum nonlocal game , where players are allowed to share arbitrarily many copies -dimensional noisy MESs , there exists an explicitly computable bound such that it suffices for the players to share copies of to achieve the winning probability at least . Thus it is feasible to approximate the quantum value of the game to arbitrarily precision.
As mentioned above, the class of noisy MESs includes , where and is an EPR state. It is as hard as Halting problem to approximate proved by [23, 24]. Therefore, our result implies that the hardness of fully quantum nonlocal games is also not robust against the noise in the preshared states.
This result generalizes [36] where the authors proved that it is feasible to approximate the values when both questions and answers are classical. Both works are built on the series of works for the decidability of non-interactive simulations of joint distributions [17, 16, 12]. In the setting of non-interactive simulations of joint distributions, two non-communicating players Alice and Bob are provided a sequence of independent samples from a joint distribution , where Alice observes and Bob observes . The question is to decide what joint distribution Alice and Bob can sample. The research on this problem has a long history and fruitful results (see, for example [26] and the references therein). The quantum analogue was first studied by Delgosha and Beigi [13], which is referred to as local state transformation. The decidability of local state transformation is still widely open. In this work, we prove that the local state transformation is decidable when the source states are noisy MESs.
1.1 Contributions
The main contribution in this paper is developing a Fourier-analytic framework for the study of the space of super-operators. Here we list some conceptual or technical contributions, which are believed to be interesting in their own right and have further applications in quantum information science.
-
1.
Analysis in the space of super-operators.
The space of super-operators is difficult to understand in general. In this paper, we make a crucial observation that the quantum value of a fully quantum nonlocal game can be reformulated in terms of the Choi representations of the adjoint maps of the quantum operations. Instead of the space of super-operators, we apply Fourier analysis to the space spanned by those Choi representations. Then we prove an invariance principle for super-operators as well as a dimension reduction for quantum operations, which generalize the analogous results in [36].
Our understanding of Fourier analysis in the space of super-operators is still very limited, although Boolean analysis has been studied extensively in both mathematics and theoretical computer science for decades. The approach taken in this paper may pave the way for the theory of Fourier analysis in the space of super-operators.
-
2.
Invariance principle for super-operators.
The classical invariance principle is a central limit theorem for polynomials [32], which asserts that the distribution of a low-degree and flat polynomial with random inputs uniformly drawn from is close to the distribution which is obtained by replacing the inputs with i.i.d. standard normal distributions. Here a polynomial is flat means that no variable has high influence on the value of the polynomial. In [36], the authors established an invariance principle for matrix spaces. This paper further proves an invariance principle for super-operators. This is essential to reduce the number of shared noisy MESs.
-
3.
Dimension reduction for quantum operations.
An important step in our proof is a dimension reduction for quantum operations, which enables us to reduce the dimensions of both players’ quantum operations. It, in turn, reduces the number of noisy MESs shared between the players. Dimension reductions for quantum operations are usually difficult and sometimes even impossible [19, 39]. In this paper, we prove a dimension reduction via an invariance principle for super-operators and the dimension reduction for polynomials in Gaussian spaces [16]. we adopt the techniques in [16] with a delicate analysis. It leads to an exponential upper bound in the main theorem. which also improves the doubly exponential upper bound in [36].
1.2 Comparison with [36]
In [36], the authors applied Fourier analysis to the Hilbert space where both players’ measurements stay, and proved hypercontractive inequalities, quantum invariance principles and dimension reductions for matrices and random matrices. In a fully quantum nonlocal game, both players perform quantum operations. Hence, a natural approach is to further extend the framework in [17, 36] to the space of super-operators.
The first difficulty occurs as the answers are quantum. In [36], the authors applied the framework to each pair of POVM elements (one from Alice and one from Bob). Further taking a union bound, the result concludes. Hence, it suffices to work on the space where the POVM elements stay, which is a tensor product of identical Hilbert spaces. This approach fails when considering fully quantum nonlocal games as the answers are quantum. Hence, we need to have a convenient representation of super-operators to work on. It is known that there are several equivalent representations of super-operators [42]. In this paper, we choose the Choi representations of super-operators, which view a super-operator as an operator in the tensor product of the input space and the output space. Hence, the underlying Hilbert space is a tensor product of a number of identical Hilbert spaces and the output Hilbert space. Thus, the analysis in [36] cannot be generalized here directly.
The second difficulty occurs as the questions are quantum. In [36], the authors essentially proved an upper bound on the number of noisy MESs for each pair of inputs. If the precision of the approximation is good enough, then we can obtain an upper bound for all inputs again by a union bound because the questions are finite in a nonlocal game. This argument cannot be directly generalized to fully nonlocal games as the questions are the marginal state of the input state with Alice and Bob. Fortunately, this difficulty can be avoided as the input state is in a bounded-dimensional space and thus it suffices to prove the theorem for each basis element from a properly chosen basis in the space, and then take a union bound.
The last difficulty is that the rounding argument in [36] does not apply to fully quantum nonlocal games. In the end of the construction, the new super-operators are no longer valid quantum operations. In [36], the construction gives a number of Hermitian operators in the end. The rounding argument proves that it is possible to round these Hermitian operators to valid POVMs with small deviation. For fully quantum nonlocal games we need a new rounding argument which is able to round super-operators to valid quantum operations with small deviation in the end of the construction.
1.3 Proof overview
The proof is built on the framework in [17, 16, 12] for the decidability of non-interactive simulation of joint distributions. To explain the high-level idea of our proof, we start with the decidability of a particular task of local state transformation. Then we explain how to generalize it to nonlocal games.
Local state transformation
We are interested in the decidability of the following local state transformation problem.
Given , a bipartite state and a noisy MES , suppose Alice and Bob share arbitrarily many copies of .
-
•
Yes. Alice and Bob are able to jointly generate a bipartite state using only local operations such that is -close to , i.e., .
-
•
No. Any quantum state that Alice and Bob can jointly generate using only local operations is -far from , i.e., .
As there is no upper bound on the number of copies of , the decidability of this question is unclear. If it were proved that any quantum operation could be simulated by a quantum operation in a bounded dimension, then the problem would be decidable as we could search all possible quantum operations in a bounded-dimensional space via an -net and brute force. More specifically, suppose Alice and Bob share copies of noisy MESs and they perform quantum operations and . For any precision parameter , we need to construct quantum operations and acting on copies of , where is independent of , such that
(1) |
To explain the high-level ideas, we assume that is a -qubit quantum state for simplicity. Let be an orthonormal basis in the space of matrices. We observe that the left hand side of Eq. (1) is determined by the following values:
where . Notice that
where and are the adjoints of and , respectively. Hence, Eq. (1) is equivalent to
(2) |
Eq. (2) resembles the setting considered in [36]. It is proved in [36] that for any POVM acting on , there exists POVM acting on such that
for all . However, and are not positive. It is even not clear how to characterize and for valid quantum operations and . Thus we cannot directly apply the results in [36]. Instead of working on each of and , we work on the Choi representations and , which include the information of and for all . One more advantage of Choi representations is that we have a neat characterization of the Choi representations of quantum operations (refer to 3.2). Thus it is more convenient to bound the deviations of the intermediate super-operators from valid quantum operations throughout the construction. We consider the Fourier expansions of and , and reduce the dimensions of the super-operators via the framework for the decidability of non-interactive simulations of joint distributions in [17, 16, 12, 36]. To this end, we prove an invariance principle for super-operators, and combine it with the dimension reduction for polynomials in Gaussian spaces [16]. There are several prerequisites for the invariance principle. Firstly, the Choi representation should have low degree. Secondly, all but a constant number of systems are of low influence, that is, all but a constant number of subsystems do not influence the super-operators much. The construction takes several steps to adjust the Fourier coefficients of and to meet those prerequisites. Meanwhile, the new super-operators still need to be close to valid quantum operations so that the value of the game does not change much. Once these prerequisites are satisfied, the basis elements in those subsystems with low influence are replaced by properly chosen Gaussian variables, which only causes a small deviation by the invariance principle.
The whole construction is summarized in Fig. 1. Each step is sketched as follows.
q. systems | |||||||
|
Lemma 5.1 | Lemma 5.1 | |||||
|
|||||||
|
Lemma 5.6 | ||||||
|
|||||||
|
Lemma 5.7 | Lemma 5.7 | |||||
|
|||||||
|
Lemma 5.13 | ||||||
|
|||||||
|
Lemma 5.18 | Lemma 5.18 | |||||
|
|||||||
|
Lemma 5.20 | Lemma 5.20 | |||||
|
|||||||
|
Lemma 5.12 | Lemma 5.12 | |||||
|
|||||||
|
Lemma 5.23 | Lemma 5.23 | |||||
|
-
1.
Smoothing
Suppose that Alice and Bob perform quantum operations and , respectively. Let be the adjoints of (defined in Eq. 5), respectively, and be the corresponding Choi representations (defined in Eq. 6). Notice that lie in the tensor-product space of the input Hilbert space and the output Hilbert space. The output Hilbert space is bounded-dimensional. And the input Hilbert space is unbounded, of which we aims to reduce the dimension.
This step is aimed to obtain bounded-degree approximations of and . We apply a noise operator for some defined in Definition 3.15 to both and on the input spaces. Note that both Choi representations are positive operators. After smoothing the operation and truncating the high-degree parts, we get bounded-degree approximations and , of and , respectively. Though the bounded-degree approximations may no longer be positive, the deviation can be proved to be small.
-
2.
Regularity
This step is aimed to prove that the number of subsystems having high influence is bounded. The influence of a subsystem of a multipartite Hermitian operator is defined in Definition 3.4. Informally speaking, the influence measures how much the subsystem can affect the operator. For a bounded operator, the total influence, which is the summation of the influences of all subsystems, is upper bounded by the degree of the operator. This is a generalization of a standard result in Boolean analysis. Note that we have bounded-degree approximations after the first step. The desired result follows by a Markov inequality.
-
3.
Invariance principle
In this step, we use correlated Gaussian variables to substitute the basis elements in all the subsystems with low influence in and , after which we get random operators and , whose Fourier coefficients are low-degree multilinear polynomials in Gaussian variables. We also need to prove that, and are close to positive operators in expectation.
-
4.
Dimension reduction
This step is aimed to reduce the number of Gaussian variables. After applying a dimension reduction to and , we get random operators and containing a bounded number of Gaussian random variables. Unlike [36], we get an upper bound independent of the number of quantum subsystems via a more delicate analysis. However, the Fourier coefficients of and are no longer low-degree polynomials after the dimension reduction.
-
5.
Smooth random operators
The remaining steps are mainly concerned with removing the Gaussian variables. This step is aimed to get low-degree approximations of the Fourier coefficients of and . We apply the Ornstein-Uhlenbeck operator (aka noise operators in Gaussian space, see Definition 3.6) to the Gaussian variables in and and truncate the high-degree parts to get and . We should note that the Fourier coefficients of and are polynomials, but not multilinear.
-
6.
Multilinearization
This step is aimed to get multilinear approximations of the Fourier coefficients of and . To this end, We apply the multilinearization lemma in [16] to get random operators and . Now we are ready to use the invariance principle again to convert random operators back to operators.
-
7.
Invariance to operators
In this step we substitute the Gaussian variables with properly chosen basis elements, to get operators and , which have a bounded number of quantum subsystems. Again, we need to apply a quantum invariance principle to ensure that and are close to positive operators.
-
8.
Rounding
We now have operators and that are close to positive operators. The last thing to do is to round them to the Choi representations of the adjoints of some quantum operations. After the rounding, the whole construction is done.
From local state transformation to fully quantum nonlocal games
In the setting of a fully quantum nonlocal game, Alice and Bob share noisy MESs as well as an input state which may be entangled with the referee. Thus, it can be reformulated as the following problem.
Given , a tripartite state , a noisy MES and a tripartite state , suppose Alice, Bob and referee share . Additionally, Alice and Bob also share arbitrarily many copies of .
-
•
Yes. Alice and Bob are able to jointly generate a tripartite state among Alice, Bob and the referee using only local operations such that is -close to , i.e., .
-
•
No. Any tripartite state among Alice, Bob and the referee that Alice and Bob can jointly generate using only local operations is -far from , i.e., .
In both cases, the referee does not perform any quantum operation.
Suppose the input state is in the register , the target state is in the register , and Alice and Bob share copies of noisy MES’s, i.e., . They perform quantum operations and , respectively, where and . For any precision parameter , we need to construct quantum operations acting on copies of together with , and acting on copies of together with , such that
(3) |
where is independent of . It is illustrated in Fig. 2.
|(PA)| & |(PB)| [3em]
|(A)| |(B)| |(A2)|Alice |(B2)|Bob
|(R)|Referee |(R2)|Referee
|(TA)| |(TB)|
|(A3)| |(B3)|
|(R3)|Referee
;
:[swap]A "":- B; \morA :- R; \morB :- R; \mor:[shove=+2em] B -> A2; \morA2 :- B2; \morA2 :- R2; \morB2 :- R2; \mor:[shove=-1.5em,dashed] PA :- PB; \mor:[shove=+1.5em,dashed] PA - PB; \mor:[shove=-.5em,dashed] PA - PB; \mor:[shove=+.5em,dashed] PA - PB; \mor:[shove=+1.5em,dashed] TA - TB; \mor:[shove=-1.5em,dashed] TA :- TB; \mor:[shove=-.5em,dashed] TA - TB; \mor:[shove=+.5em,dashed] TA - TB; \morA3 :- B3; \morA3 :- R3; \morB3 :- R3; \mor:[swap]A3 "":- B3; \mor:[swap]A2 "":- B2; \nodeat (-3.3,0.4) ; \nodeat (-5.8,3.9); \nodeat (-1,3.9); \nodeat (-5.8,-1.4); \nodeat (-1,-1.4); \draw(-7,5.5) – (-7,-4.5) – (5.5,-4.5) – (5.5,5.5) – (-7,5.5);
Let be an orthogonal basis in . Then the left-hand side of Eq. (3) is determined by the following set of values
By the fact that , we have
(4) |
where . Notice that the difference between Eq. (4) and Eq. (1) is that there is an additional operator , which is a bounded-dimensional operator, but probably not a quantum state. We can still work on the Fourier expansions of the Choi representations and . We will show that the framework for local state transformation still works even if there is an additional bounded-dimensional operator .
2 Open problems
In this work, we prove computable upper bounds on local state transformations with noisy MESs as source states. With some extra work, we further obtain computable upper bounds on the preshared entanglement for fully quantum nonlocal games where the players are only allowed to share noisy MESs. This implies that fully quantum nonlocal games with noisy MESs are decidable. We now list some interesting open problems for future work.
-
1.
If we compute the quantum values by -netting and searching over all the strategies, then the running time is at least doubly exponential in the size of the games. Can the upper bound on the entanglement or the time complexity be improved? It would be interesting to understand the exact complexity of fully quantum nonlocal games with noisy MESs. From the complexity-theoretic point of view, we may further investigate the complexity classes and . Here is the set of languages that can be decided by entangled multiprover interactive proof systems, where the provers are only allowed to share arbitrarily many copies of and the provers exchange classical messages with verifiers. If the messages are quantum, then the class is . What is the exact computational power of these complexity classes for constant-sized states ? We only know the answer if is an EPR state, for which it is RE, or a separable state, for which it is NEXP. When is a noisy entangled quantum state, would the computational power increase when the players share more copies of ? To what extent is the computational power of entangled multiprover interactive proof systems robust against noise?
-
2.
Local state transformation is one of the most basic quantum communication tasks. Beigi [1] initiated the study of the decidability of local state transformation and proved several sufficient conditions and necessary conditions [1, 13]. However, to the best of our knowledge, this problem is still widely open. There are many other communication tasks with similar settings, which are also not well understood. For example, distillable entanglement measure and entanglement formation measure are two of the most well-studied entanglement measures [3] defined in a similar setting. The only difference in this setting is that classical communication between the players is free, and we aim to optimize the ratio between the number of target states and the number of source states. After decades of efforts, we still don’t know how to compute the distillable entanglement measure or the entanglement formation measure of a given state. It is tempting to see whether the framework in this paper could provide new insights into the computability of these quantities.
-
3.
There are several "tensored" quantities in quantum information theory that are not known how to compute, such as quantum channel capacities [18], various regularized entanglement measures [20] and quantum information complexity [40]. Some of them look extremely simple but turn out to be notoriously hard, such as the quantum channel capacities of depolarizing channels [29]. Can we use the framework in this paper to design algorithms for these quantities?
-
4.
Given the wide range of applicability of Boolean analysis, Montanaro and Osborne initiated the study of its extensions to quantum setting, where they introduced quantum boolean functions [31]. Several key concepts and results have been successfully generalized to the quantum setting (readers may refer to the introduction in [38] for more details). Some fundamental problems are still open, such as quantum KKL conjecture [31, 38]. Meanwhile, Fourier analysis in quantum settings has found applications in various topics, such as quantum communication complexity [2], circuit complexity [6], property testing of unitary operators [41], learning quantum juntas [9], learning quantum dynamics [38], etc. It is fascinating to see more applications of this growing field in quantum information and quantum computation.
Acknowledgements
The authors thank Zhengfeng Ji for helpful discussion. This work was supported by National Natural Science Foundation of China (Grant No. 61972191), Innovation Program for Quantum Science and Technology (Grant No. 2021ZD0302900) and the Program for Innovative Talents and Entrepreneur in Jiangsu.
3 Preliminary
For readers’ convenience, we list all the notations used in this paper in Appendix A. Given , let and represent the sets and , respectively. For all , we define . In this paper, the lower-cased letters in bold are reserved for random variables, and the capital letters in bold are reserved for random operators.
Convention 3.1.
We use to represent quantum systems, and the basis in the system is represented by the same letter in the calligraphy font. For instance, the basis in the quantum system is represented by . The dimension of quantum systems are denoted by , respectively. To keep notations short, the dimension of a quantum system is also represented by the corresponding lower-cased letter in the sans serif font, e.g., the dimensions of quantum systems may be also represented by ,, respectively.
3.1 Quantum mechanics
We first review the formalism of quantum mechanics. Readers may refer to [34, 42] for a thorough treatment. A quantum system is associated with a finite-dimensional Hilbert space, known as the state space of the system. We consider the space of linear operators acting on the states and equip the space with the normalized Hilbert-Schmidt inner product
where denotes the conjugate transpose of and is the dimension of .
A quantum state in can be completely described by a density operator, which is a positive semi-definite operator with trace one. We denote the set of all linear operators in the state space by , and the set of Hermitian operators by . The identity operator is denoted by . If the dimension of is , we may write or . The subscripts and may be dropped whenever it is clear from the context. The state of a composite quantum system is the Kronecker product of the state spaces of the component systems. In this paper, we use the shorthand to represent . A state of a composite system with two components is called a bipartite state. The Hermitian space of the composition of Hermitian space is denoted by , or for short. Quantum measurements are described by a POVM, that is, a number of positive operators summing to identity. The index refers to the measurement outcomes that may occur in the experiment. If the state of the quantum system is immediately before the measurement then the probability that result occurs is given by .
Given quantum systems , let denote the set of all linear maps from to , and if the input system and the output system are the same, we write for simplicity. A quantum operation from the input system to the output system is represented by a CPTP (completely positive and trace preserving) map . An important example of quantum operations is partial trace. Given quantum systems , and a bipartite state ( for short), the partial trace derives the marginal state of the subsystem from . The partial trace is given by
where is an orthonormal basis in . It is easy to verify that the operation is independent of the choice of basis .
For a given map , the adjoint of is defined to be the unique map that satisfies
(5) |
for all and .
Given , the Choi representation of is a linear map defined as follows:
(6) |
where 111The denominator is because of the demoninator in the definition of the inner product , and is an orthonormal basis in . In [42] the Choi representation is defined using the basis , where the -entry of is and the others are . It is easy to verify that the definition is independent of the choice of basis. is a linear bijection. can be recovered from its Choi representation as follows.
(7) |
Fact 3.2.
[42] Given , the following three statements are equivalent.
-
1.
is completely positive.
-
2.
is completely positive.
-
3.
.
And the following four statements are equivalent as well.
-
1.
is trace preserving.
-
2.
is unital, that is, .
-
3.
.
-
4.
.
Proof.
For the first part, item 1 and item 2 are equivalent by definition. Item 3 is equivalent to item 1 is by Theorem 2.22 in [42]. For the second part, item 1 and item 2 are equivalent by definition. Item 1 and item 3 are equivalent by Theorem 2.26 in [42]. To see the equivalence between item 2 and item 4, let be an orthonormal basis in with . By the definition of the Choi representation,
where the second equality is by the orthonormality of and our choice . It is easy to see item 2 and item 4 are equivalent. ∎
By the above fact, is a quantum operation if and only if and .
We also need the following fact.
Fact 3.3.
[36, Fact 2.1] Given quantum systems , operators and a bipartite state , it holds that
-
1.
;
-
2.
.
3.2 Fourier analysis in Gaussian space
Given , let represent a standard -dimensional normal distribution. A function is in if
All the functions involved in this paper are in . We equip with an inner product
Given , the 2-norm of is defined to be
The set of Hermite polynomials forms an orthonormal basis in with respect to the inner product . The Hermite polynomials for are defined as
For any , define as
The set forms an orthonormal basis in . Every function has an Hermite expansion as
where ’s are the Hermite coefficients of , which can be obtained by . The degree of is defined to be
We say is multilinear if for .
Definition 3.4.
Given a function , the variance of is defined to be
The influence of the -th coordinate(variable) on , denoted by , is defined by
The following fact summarizes some basic properties of variance and influence.
Fact 3.5.
[35, Proposition 8.16 and Proposition 8.23] Given , it holds that
-
1.
-
2.
Definition 3.6.
Given and , we define the Ornstein-Uhlenbeck operator to be
Fact 3.7.
[35, Page 338, Proposition 11.37] For any and , it holds that
A vector-valued function is in if for all . The -norm of is defined to be
The action of Ornstein-Uhlenbeck operator on is defined to be
(8) |
Given , denotes the distribution of -correlated Gaussians, that is,
Given , we denote
3.3 Fourier analysis in matrix space
Given , and , the -norm of is defined to be
where . It is easy to verify that for ,
(9) |
The normalized -norm of is defined as
For , by Eq. 9, we have
(10) |
Given , we define an inner product over :
We need the following particular classes of bases in on which our Fourier analysis is based.
Definition 3.8.
Let be an orthonormal basis in over . We say is a standard orthonormal basis if .
Fact 3.9.
Let be a standard orthonormal basis in . Then
is a standard orthonormal basis in .
Given a standard orthonormal basis in , every has a Fourier expansion:
where are the Fourier coefficients. The basic properties of ’s are summarized in the following fact, which can be easily derived from the orthonormality of .
Fact 3.10.
[36, Fact 2.11] Given a standard orthonormal basis in and , it holds that
-
1.
.
-
2.
.
-
3.
.
Definition 3.11.
Let be a standard orthonormal basis in ,
-
1.
The degree of is defined to be
Recall that represents the number of nonzero entries of .
-
2.
For any , the influence of -th coordinate is defined to be
(11) where is in the ’th quantum system, and the partial trace derives the marginal state of the remaining quantum systems except for the ’th one.
-
3.
The total influence of is defined to be
Fact 3.12.
[36, Lemma 2.16] Given , a standard orthonormal basis in , it holds that
-
1.
-
2.
With the notion of degrees, we define the low-degree part and the high-degree part of an operator.
Definition 3.13.
Given , a standard orthonormal basis in and , we define
and
where ’s are the Fourier coefficients of with respect to the basis .
Fact 3.14.
[36, Lemma 2.15] The degree of is independent of the choices of bases. Moreover, and are also independent of the choices of bases.
Definition 3.15.
Given a quantum system with dimension , , the depolarizing operation is defined as follows. For any ,
Fact 3.16.
[36, Lemma 3.6 and Lemma 6.1] Given , , a standard orthonormal basis of : , the following holds:
-
1.
For any with a Fourier expansion , it holds that
-
2.
For any , .
-
3.
is a quantum operation.
-
4.
For any , it holds that
Definition 3.17 (Maximal correlation).
[1] Given quantum systems with dimensions and , with , the maximal correlation of is defined to be
Fact 3.18.
[1] Given quantum systems with dimensions and , with , it holds that .
Definition 3.19.
Given quantum systems with dimensions and , a bipartite state is a noisy maximally entangled state (MES) if and its maximal correlation .
Beigi proved that depolarized maximally entangled states are noisy maximally entangled states.
Fact 3.20.
Fact 3.21.
[36, Lemma 7.3] Given quantum systems with dimensions and , if is a noisy MES with maximal correlation , then there exist standard orthonormal bases and in and , respectively, such that
(12) |
where and .
As described in Section 1.2, one of the difficulties is that the input of a fully quantum nonlocal game is a tripartite quantum state. The following lemma enables us to ’discretize’ the input state by properly chosen orthonormal bases.
Lemma 3.22.
Given quantum systems with , an orthonormal basis in , a tripartite quantum state and an integer , there exist orthonormal bases and in and , respectively, which may depend on , such that
(13) |
where , , and . 222Assume without loss of generality. If , then
Remark 3.23.
Notice that are not required to be standard orthonormal bases.
Proof of Lemma 3.22.
Let and be arbitrary orthonormal bases in and , respectively. Let be a matrix such that
Then is a real matrix. Thus, it has a singular value decomposition
where and are orthonormal matrices (i.e., real unitary matrices) and is a diagonal matrix with diagonal entries non-negative. Define
and
Then and are orthonormal bases as well. We have
In particular, since , and are orthonormal bases,
Eq. 13 holds. ∎
3.4 Random operators
In this subsection, we introduce random operators defined in [36], which unifies Gaussian variables and operators.
Definition 3.24.
[36] Given , we say is a random operator if it can be expressed as
where is a standard orthonormal basis in , for all and if for all . Define a vector-valued function
We say is the associated vector-valued function of under the basis .
The degree of , denoted by , is
We say is multilinear if is multilinear for all .
Fact 3.25.
[36, Lemma 2.23] Given , let with an associated vector-valued function under a standard orthonormal basis. It holds that
We say a pair of random operators are joint random operators if the random variables in are drawn from a joint distribution for .
3.5 Rounding maps
Given a closed convex set , the rounding map of , denoted by , is defined as follows:
The following well-known fact states that the rounding maps of closed convex sets are Lipschitz continuous with Lipschitz constant being 1.
Fact 3.26.
[4, Page 149, Proposition 3.2.1] Let be a nonempty closed convex set in with the rounding map . It holds that
for any .
Define a function as follows.
(14) |
The function measures the distance between an Hermitian operator and the set of positive semi-definite operators in -norm.
Fact 3.27.
[36, Lemma 9.1] Given , , it holds that
Fact 3.28.
[36, Lemma 10.4] For any Hermitian matrices and , it holds that
4 Main results
Theorem 4.1.
Given , , and quantum systems with dimensions Let , , be orthonormal bases in , and , respectively. Let be a noisy MES with the maximal correlation , which is defined in Definition 3.17. Let be an arbitrary tripartite quantum state. Then there exists an explicitly computable , such that for all quantum operations , , there exist quantum operations , such that for all , , , 333Remind that , and .
In particular, one may choose
Theorem 4.2.
Given parameters , and a fully quantum nonlocal game
with dimensions , suppose the two players are restricted to share an arbitrarily finite number of noisy MES states , i.e., , with the maximal correlation as defined in Definition 3.17. Let be the supremum of the winning probability that the players can achieve. Then there exists an explicitly computable bound such that it suffices for the players to share copies of to achieve the winning probability at least . In particular, one may choose
Proof.
To keep the notations short, the superscripts will be omitted whenever it is clear from the context. Suppose the players share copies of and employ the strategy with the winning probability . We apply Theorem 4.1 to with to obtain . We claim that the strategy wins the game with probability at least .
Let , , be orthonormal bases in , and , respectively. From Theorem 4.1, for all , , , we have
By Eq. 5, it is equivalent to
∎
4.1 Notations and setup
The proof of Theorem 4.1 involves a number of notations. To keep the proof succinct, we introduce the setup and the notations that are used frequently in the rest of the paper. Some of the notations have been defined in Theorem 4.1. We collect them here for readers’ convenience.
The notations used to represent quantum systems, bases, dimensions and operators are summarized in Table 1 following 3.1.
System | |||||||
---|---|---|---|---|---|---|---|
Basis | |||||||
Dimension | |||||||
Operator | M | N |
Setup 4.3.
Given quantum systems with dimensions
let be the input state in shared among Alice, Bob and the referee, where Alice, Bob and the referee hold , and , respectively. Let be the noisy MES shared between Alice and Bob, where Alice has and Bob has . Let be the maximal correlation of . Let and be the answer registers of Alice and Bob, respectively.
Let be standard orthonormal bases in , respectively. Let be orthonormal bases (not necessary to be standard orthonormal) in , respectively. We require that and satisfy Eq. 12. For convenience, we denote to be . The same for , , , .
When we use universal quantifiers, we omit the ranges of the variables whenever they are clear in the context. For example, we say “for all , ” to mean “for all , ”.
Given , for all , we define to be , and to be . Similar for . In other words,
(15) |
and
(16) |
4.2 Proof of Theorem 4.1
Proof of Theorem 4.1.
Let be parameters which are chosen later. The proof is composed of several steps.
-
•
Smoothing
We apply Lemma 5.1 to and with to get and , respectively. They satisfy the following.
-
•
Regularization
Applying Lemma 5.6 to and with , we obtain of size such that for all :
-
•
Invariance to random operators
Applying Lemma 5.7 to , and , we obtain joint random operators and satisfying the following.
-
1.
For all :
-
2.
For all :
-
3.
and
-
4.
and .
-
1.
-
•
Dimension Reduction
Applying Lemma 5.13 to with , , , , if we sample , then item 1 to 3 in Lemma 5.13 hold with probability at least . Thus we get joint random operators such that the following holds:
-
1.
For all :
-
2.
-
3.
For all :
-
4.
and .
Here .
-
1.
-
•
Smoothing random operators
Applying Lemma 5.18 to with , we obtain joint random operators satisfying the following.
-
1.
For all :
-
2.
For all :
-
3.
-
4.
For all :
-
5.
and .
Here .
-
1.
-
•
Multilinearization
Suppose that
We apply Lemma 5.20 to with , we obtain multilinear random operators such that the following holds:
-
1.
For all , and are degree- multilinear random operators.
-
2.
Suppose that
where . For all ,
-
3.
For all :
-
4.
and
-
5.
For all :
-
6.
and .
Here .
-
1.
-
•
Similarly, we have
Let
We apply Lemma 5.12 to with to get satisfying that:
-
1.
For all :
-
2.
For all :
-
3.
and
-
4.
and .
-
1.
-
•
Rounding
Applying Lemma 5.23 to and , we get and satisfying
(17) (18)
Keeping track of the parameters in the construction, we are able to upper bound and . Finally, by the triangle inequality we are able to upper bound
The dependency of the parameters is pictorially described in Fig. 3.
&[11em] |(B)| Smoothing (Lemma 5.1) [14em]
|(H)| |(C)| Regularization (Lemma 5.6)
|(A)| in Eq. 19 Given |(D)| Dimension reduction (Lemma 5.13) |(E)|
|(F)| Smoothing random operators (Lemma 5.18)
|(G)| Multilinearization (Lemma 5.20)
; \mor:[swap] H determines:-> A; \mor:[bend left = 40] A δ←δ:-> B; \mor:[bend left = 20] * θ←θ:-> C; \mor* δ←δ/4()^2:-> D; \mor:[bend right = 20] * δ←δ:-> F; \mor:[bend right = 40] * δ←θ:-> G; \morB d←d_1=O:-> C; \mor:[bend left = 20] C h≤d_1(+)/θ:-> E; \mor:D n_0=O :-> *; \morF d←d_2=O :-> G; \mor:[swap, bend right = 40] G n_1=O :-> E; \mor:[swap, bend right = 20, shove = +3.1em] B [" "] :-> D;
We define , as follows:
just as Eq. 7. Let and . Then by 3.2, and are quantum operations. Furthermore,
Choosing
(19) |
we finally conclude the result. ∎
5 Construction
Theorem 4.1 states that, given an arbitrarily dimensional strategy, it can be simulated by a strategy with a bounded number of shared noisy maximally entangled states. This section focuses on the construction of the new strategies, which consists of several steps. We adopt the notations and the setup given in Section 4.1.
5.1 Smoothing
Lemma 5.1.
Given 4.3, let , . There exists an explicitly computable and maps , such that for all quantum operations , denoting and , the operators and satisfy the following.
- 1.
-
2.
For all :
-
3.
For all , and have degree at most , where and are defined in Eq. (16).
-
4.
where is defined in Eq. 14.
-
5.
and .
In particular, one may take .
Remark 5.2.
Proof of Lemma 5.1.
By Eq. 15 and the definition of the Choi representation in Eq. 6, we have
for all . By Lemma 5.3, and .
Define parameters
Set
where the noise operator acts on . Similarly, define
where the noise operator acts on . That is, for all ,
For all , define
(20) |
Each item in Lemma 5.1 is proved as follows.
- 1.
- 2.
-
3.
It holds by the definition of and in Eq. (20).
- 4.
- 5.
∎
Lemma 5.3.
Given quantum systems and , let be positive and unital, and satisfy . Then
Proof.
Since , we have . By the positivity of , . The fact that is unital implies , from which the result concludes. ∎
Lemma 5.4.
Given 4.3, let , , , . It holds that for all ,
for
where and are the depolarizing channels acting on the -copies of systems and , respectively.
In particular, there exists an absolute constant such that it suffices to take
Proof.
By Lemma 3.22, for any , we may choose bases , satisfying Eq. 13. Suppose that for all , and have Fourier expansions
Lemma 5.5.
Given , operators satisfying that for all ,
where and are defined in Definition 3.13 and Eq. (16). it holds that
5.2 Regularization
Lemma 5.6.
Given 4.3, let , , operators and satisfy that have degree at most for all . Furthermore, , for all . Then there exists a subset of size such that for all -th or system, ,
Proof.
Set
of size . Then
Similarly,
is of size . Define , the conclusion holds by a union bound. ∎
5.3 Invariance principle
The following is the main result in this subsection.
Lemma 5.7.
Given 4.3, let , , of size . There exist maps and satisfying the following.
For any , we define
If satisfy that
-
1.
For all , and ;
-
2.
For all , and have degree at most ;
-
3.
For all , , ;
-
4.
,
where and are defined in Eq. (15), then the following holds:
-
1.
For all , and are degree- multilinear joint random operators with the joint random variables drawn from , where and are defined in Eq. (16).
-
2.
For all :
-
3.
For all :
-
4.
and
-
5.
and .
Before proving the lemma, we need to introduce the quantum invariance principle for the function defined as Eq. 14.
Definition 5.8.
Given , for all multilinear random operator , assume that for all ,
where , and is multilinear for all . For all , define
The following is the quantum invariance principle for the function .
Lemma 5.9.
[36, Lemma 10.10]444The statement is slightly different from that of [36]. But the proof is exactly the same. Given 4.3, let , , of size , with the expansion as Eqs. (15)&(16) satisfies the following.
-
1.
For all , .
-
2.
For all , have degree at most .
-
3.
For all ,
Suppose has a Fourier expansion
Define
Then it holds that
where is defined in Definition 5.8.
The following is a hypercontractive inequality for random operators in .
Lemma 5.10.
The following lemma generalizes the hypercontractivity above to the operators in space .
Lemma 5.11.
Given 4.3, let and a random operator . Suppose
for any where , is a multilinear polynomial, and for all . Then
Namely, , where is defined in Definition 5.8.
Proof.
where () is by Lemma 5.10 and Eq. 10, and () is by the well-known fact that for all . ∎
We are now ready to prove Lemma 5.7.
Proof of Lemma 5.7.
Suppose for all , and have Fourier expansions
and
By the convention in 4.3, and are standard orthonormal bases in and , respectively, which satisfy Eq. (12).
Without loss of generality, we assume that . We further assume for now that the Gaussian random variables with different correlations are allowed. This assumption will be removed later. Define independent joint random variables , where for all , for all , and is defined in Eq. 12.
Define
(22) |
and
(23) |
where and are standard orthonormal bases in and , respectively, which satisfy Eq. (12), by the convention in 4.3. Then we have the correlation matching:
(24) |
for and .
Each item in Lemma 5.7 is proved as follows.
- 1.
-
2.
By direct calculation, we have
and
- 3.
-
4.
It holds by Lemma 5.9 and Lemma 5.11.
-
5.
It holds trivially by the definition of and .
It remains to show that, given , can be simulated by sampling from . Indeed, let and be drawn from independently. Define
Then . It is easy to see that all the items still hold with the replacement.
∎
The following lemma converts random operators to operators.
Lemma 5.12.
Given , , of size , there exist maps such that the following holds:
Let be any joint random operators with the expansions as Eqs. (15)&(16) satisfying the following.
-
1.
For all , and .
-
2.
For all , and are degree- multilinear random operators.
-
3.
For all , suppose that
where , and and are standard orthonormal bases in and , respectively, which satisfy Eq. (12), it holds that
-
4.
.
Then
satisfies the following.
-
1.
For all :
-
2.
For all :
-
3.
and
-
4.
and .
Proof.
For all , since and are multilinear random operators, we can assume that
where , for all . Then and can be expressed as
Define
Each item of Lemma 5.12 is proved as follows.
-
1.
By direct calculation, we have
and
-
2.
By the same argument as item 3 in the proof of Lemma 5.7, we have
-
3.
Observe that for all ,
where is by Eq. 11 combined with direct calculation.
Similarly, . Then from Lemma 5.9 and Lemma 5.11, item 3 holds.
-
4.
It follows immediately from the constructions of and .
∎
5.4 Dimension reduction
The following is the main result in this subsection.
Lemma 5.13.
Given 4.3, let ,
be degree- multilinear joint random operators satisfying the following.
-
1.
For all ,
(25) where , ,, , for all ;
-
2.
For all , and ;
-
3.
and .
Then there exists an explicitly computable and maps , for , such that the following holds:
and
where is the ’th row of . If we sample , then with probability at least , the following holds:
-
1.
For all :
-
2.
-
3.
For all :
-
4.
and .
In particular, one may take .
Remark 5.14.
To keep the proof succinct, we define for ,
Remind that the randomness of and is from the random variables and , respectively.
To prove Lemma 5.13 item 3, we need the following lemma.
Lemma 5.15.
Given 4.3, let . There exists such that the following holds for all : For ,
In particular, one may take .
We borrow the following technical lemma from [16].
Lemma 5.16.
[16, Lemma A.8, Lemma A.9] Given parameters , and , there exists an explicitly computable such that the following hold:
-
1.
For all subsets satisfying , it holds that
-
2.
For all subsets satisfying , it holds that
Here, is the symmetric difference of the sets .
In particular, one may take
Proof of Lemma 5.15.
By Lemma 3.22, for any , we can choose bases , satisfying Eq. 13. Applying Lemma 5.16 with parameters and , we have
where is by Eq. 13, is by Lemma 5.16 item 1, is by 3.3 and Lemma 3.22, and is by Eq. 16 and Eq. 25.
Using Lemma 5.16 with parameters and , we have
where is by Lemma 5.16 item 2, 3.3 and Lemma 3.22.
For all , define functions over the boolean hypercube as,
By the hypercontractive inequality [35, Page 243, Bonami Lemma]
we finish the proof as follows.
The following fact is for item 1 in Lemma 5.13.
Fact 5.17.
[16, Theorem 3.1] Given parameters , and , there exists an explicitly computable such that the following holds:
For all and any degree- multilinear polynomials , and , define functions as
Then
If and are identical and , we have
In particular, one may take .
Proof of Lemma 5.13.
Rewrite
and
where is a degree- multilinear polynomial and for all . By the definition of , we have . Each item in Lemma 5.1 is proved as follows.
-
1.
By 5.17, with probability at least , we get
Similarly, , so item 1 holds.
-
2.
We first observe that for all fixed , the distribution of is identical to that of a standard -variate Gaussian distribution. Thus, we immediately have that,
Thus, using Markov’s inequality, we get that with probability at least
-
3.
We invoke Lemma 5.15 with and . Using Chebyshev’s inequality and the Variance bound in Lemma 5.15, we have that for all ,
Using the triangle inequality, and the Mean bound in Lemma 5.15, we get
-
4.
It follows directly by the construction of and .
Items 1 to 4 hold simultaneously with probability by a union bound. ∎
5.5 Smoothing random operators
Lemma 5.18.
Given 4.3, let ,
be joint random operators with the expansions Eqs. (15)&(16), where
(26) |
Suppose they satisfy that
-
1.
;
-
2.
For all , , ;
-
3.
and .
Then there exists an explicitly computable and maps such that
satisfies the following.
-
1.
For all :
-
2.
For all :
-
3.
-
4.
For all :
-
5.
and .
In particular, one may take .
To prove Lemma 5.18, we need the following fact.
Fact 5.19.
[16, Lemma 4.1] Let be any given constant parameters, ; be closed convex sets. Set and be rounding maps of and , respectively. Then there exists explicitly computable such that the following holds:
-
1.
For all , it holds that
-
2.
and
-
3.
For all ,
-
4.
For all ,
In particular, one may take
We are now ready to prove Lemma 5.18.
Proof of Lemma 5.18.
Set
For any , let , where is the Ornstein-Uhlenbeck operator defined in Definition 3.6 and Eq. 8. For all , define
(27) |
Set vector-valued functions and . Each item in Lemma 5.18 is proved as follows:
-
1.
It follows directly by the definition of and .
-
2.
We apply 3.25 and 5.19 item 1,
where is the associated vector-valued function (in Definition 3.24) of . Similarly, .
-
3.
Combined with Eq. 29, we conclude the first inequality in item 3. The second inequality follows by the same argument.
- 4.
-
5.
It follows directly by the definition of and .
∎
5.6 Multilinearization
Lemma 5.20.
Given 4.3, let ,
be joint random operators with
as defined in Eqs. (16) satisfying that
-
1.
.
-
2.
For all , and .
-
3.
For all , .
-
4.
and .
Then there exists an explicitly computable and maps such that
satisfies the following:
-
1.
For all , and are degree- multilinear random operators.
-
2.
Suppose that
where . For all ,
-
3.
For all :
-
4.
and
-
5.
For all :
-
6.
and .
In particular, one may take .
We need the following notion introduced in [16] before constructing and .
Definition 5.21.
[16] Suppose is given with a Hermite expansion
The multilinear truncation of is defined to be the function given by
The following fact is crucial to our proof.
Fact 5.22.
Let be degree- polynomials. There exist polynomials over variables
satisfying the following:
-
1.
and are multilinear with degree .
-
2.
and .
-
3.
Given two independent random variables and , the distributions of and are identical and the distributions of and are identical.
-
4.
and .
-
5.
For all , it holds that
-
6.
.
In particular, we may take
We are now ready to prove Lemma 5.20.
Proof of Lemma 5.20.
Take . For all , applying 5.22 to and with , we get and . Let and . Each item of Lemma 5.20 is proved as follows.
-
1.
It is implied by 5.22 item 1.
-
2.
It is implied by 5.22 item 5.
- 3.
-
4.
We prove the first inequality in item 4. The second inequality follows from the same argument. Define a convex set
and let be a rounding map of . Note that , thus by 3.26, for all , we have
(30) - 5.
-
6.
It holds by the definition of and .
∎
5.7 Rounding
For a Hermitian matrix , suppose it has a spectral decomposition , where is unitary and is diagonal. Define
where is diagonal and if , and , otherwise. Let be the Moore-Penrose inverse of . Namely,
where is diagonal and if , and otherwise.
Lemma 5.23.
Let with and satisfy that and . Then there exists such that the following holds:
-
1.
;
-
2.
;
-
3.
.
Proof.
Let denote , and be the projector onto the support of . Note that implies . Define
It is easy to verify that satisfies item 1 and 2. To prove item 3,
∎
Claim 5.24.
Claim 5.25.
Lemma 5.26.
Let . It holds that
Proof.
Thus,
∎
Proof of 5.24.
∎
Proof of 5.25.
∎
Fact 5.27.
[43, Proposition 3.4] Let be positive, then
Fact 5.28.
[36, Lemma 9.5] Given Hermitian matrices and the following holds:
-
1.
If , then .
-
2.
If , then .
Lemma 5.29.
Given 4.3, let , and . Then for all , we have
Proof.
Appendix A List of notations
noise operator, | |
the adjoint of | |
standard -dimensional normal distribution | |
the number of nonzeros in | |
the matrix is positive semi-definite | |
for | |
for | |
-correlated Gaussian distribution | |
the set of all Hermitian operators in the system | |
the set of all Hermitian operators of dimension | |
Hermite polynomial, | |
the identity operator in the system | |
the identity operator of dimension | |
the Choi representation | |
the set of all linear maps from to | |
the set of all linear operators in the system | |
the set of all linear operators of dimension | |
the matrix is positive semi-definite | |
the transposed conjugate of | |
the -entry of | |
, Fourier coefficient of with respect to | |
the associated vector-valued function of | |
POVM | satisfying |
(similar for , , , ) | |
for all | |
partial trace, | |
for | |
where is a spectral decomposition | |
of and if and otherwise. | |
Moore-Penrose inverse of . | |
the set of all positive integers. |
References
- [1] Salman Beigi. A new quantum data processing inequality. Journal of Mathematical Physics, 54(8):082202, 2013.
- [2] A. Ben-Aroya, O. Regev, and R. d. Wolf. A hypercontractive inequality for matrix-valued functions with applications to quantum computing and ldcs. In 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pages 477–486, Oct 2008.
- [3] Charles H. Bennett, Herbert J. Bernstein, Sandu Popescu, and Benjamin Schumacher. Concentrating partial entanglement by local operations. Phys. Rev. A, 53:2046–2052, Apr 1996.
- [4] Dimitri P Bertsekas. Convex optimization algorithms. Athena Scientific Belmont, 2015.
- [5] Cyril Branciard, Denis Rosset, Yeong-Cherng Liang, and Nicolas Gisin. Measurement-device-independent entanglement witnesses for all entangled quantum states. Phys. Rev. Lett., 110:060405, Feb 2013.
- [6] Kaifeng Bu, Roy J. Garcia, Arthur Jaffe, Dax Enshan Koh, and Lu Li. Complexity of quantum circuits via sensitivity, magic, and coherence. arXiv preprint arXiv:2204.12051, 2022.
- [7] Francesco Buscemi. All entangled quantum states are nonlocal. Phys. Rev. Lett., 108:200401, May 2012.
- [8] Eric G. Cavalcanti, Michael J. W. Hall, and Howard M. Wiseman. Entanglement verification and steering when alice and bob cannot be trusted. Phys. Rev. A, 87:032306, Mar 2013.
- [9] Thomas Chen, Shivam Nadimpalli, and Henry Yuen. Testing and learning quantum juntas nearly optimally. arXiv preprint arXiv:2207.05898, 2207.05898.
- [10] Kai-Min Chung, Xiaodi Wu, and Henry Yuen. Parallel Repetition for Entangled k-player Games via Fast Quantum Search. In David Zuckerman, editor, 30th Conference on Computational Complexity (CCC 2015), volume 33 of Leibniz International Proceedings in Informatics (LIPIcs), pages 512–536, Dagstuhl, Germany, 2015. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
- [11] Richard Cleve, Peter Hoyer, Benjamin Toner, and John Watrous. Consequences and limits of nonlocal strategies. In Proceedings of the 19th IEEE Annual Conference on Computational Complexity, CCC ’04, pages 236–249, Washington, DC, USA, 2004. IEEE Computer Society.
- [12] Anindya De, Elchanan Mossel, and Joe Neeman. Non interactive simulation of correlated distributions is decidable. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’18, pages 2728–2746, Philadelphia, PA, USA, 2018. Society for Industrial and Applied Mathematics.
- [13] Payam Delgosha and Salman Beigi. Impossibility of local state transformation via hypercontractivity. Communications in Mathematical Physics, 332(1):449–476, Nov 2014.
- [14] Joseph Fitzsimons, Zhengfeng Ji, Thomas Vidick, and Henry Yuen. Quantum proof systems for iterated exponential time, and beyond. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, New York, NY, USA, 2019. ACM.
- [15] Joseph Fitzsimons and Thomas Vidick. A multiprover interactive proof system for the local hamiltonian problem. In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS ’15, page 103–112, New York, NY, USA, 2015. Association for Computing Machinery.
- [16] Badih Ghazi, Pritish Kamath, and Prasad Raghavendra. Dimension reduction for polynomials over gaussian space and applications. In Proceedings of the 33rd Computational Complexity Conference, CCC ’18, pages 28:1–28:37, Germany, 2018. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
- [17] Badih Ghazi, Pritish Kamath, and Madhu Sudan. Decidability of non-interactive simulation of joint distributions. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 545–554, Los Alamitos, CA, USA, Oct 2016. IEEE Computer Society.
- [18] L. Gyongyosi, S. Imre, and H. V. Nguyen. A survey on quantum channel capacities. IEEE Communications Surveys Tutorials, 20(2):1149–1205, Secondquarter 2018.
- [19] Aram W. Harrow, Ashley Montanaro, and Anthony J. Short. Limitations on quantum dimensionality reduction. In Luca Aceto, Monika Henzinger, and Jiří Sgall, editors, Automata, Languages and Programming, pages 86–97, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg.
- [20] Ryszard Horodecki, Paweł Horodecki, Michał Horodecki, and Karol Horodecki. Quantum entanglement. Rev. Mod. Phys., 81:865–942, Jun 2009.
- [21] Tsuyoshi Ito and Thomas Vidick. A multi-prover interactive proof for NEXP sound against entangled provers. In Proceedings of the 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, FOCS ’12, pages 243–252, Washington, DC, USA, 2012. IEEE Computer Society.
- [22] Zhengfeng Ji. Classical verification of quantum proofs. In Proceedings of the Forty-eighth Annual ACM Symposium on Theory of Computing, STOC ’16, pages 885–898, New York, NY, USA, 2016. ACM.
- [23] Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen. . arXiv preprint arXiv:2001.04383, 2020.
- [24] Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen. Quantum soundness of the classical low individual degree test. arXiv preprint arXiv:2009.12982, 2020.
- [25] Nathaniel Johnston, Rajat Mittal, Vincent Russo, and John Watrous. Extended non-local games and monogamy-of-entanglement games. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 472(2189):20160003, may 2016.
- [26] S. Kamath and V. Anantharam. On non-interactive simulation of joint distributions. IEEE Transactions on Information Theory, 62(6):3419–3435, June 2016.
- [27] J. Kempe, O. Regev, and B. Toner. Unique games with entangled provers are easy. SIAM Journal on Computing, 39(7):3207–3229, 2010.
- [28] Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Ben Toner, and Thomas Vidick. Entangled games are hard to approximate. In Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS ’08, pages 447–456, Washington, DC, USA, 2008. IEEE Computer Society.
- [29] Felix Leditzky, Nilanjana Datta, and Graeme Smith. Useful states and entanglement distillation. IEEE Transactions on Information Theory, 64(7):4689–4708, 2018.
- [30] Debbie Leung, Ben Toner, and John Watrous. Coherent state exchange in multi-prover quantum interactive proof systems. Chicago Journal of Theoretical Computer Science, 2013(11), August 2013.
- [31] Ashley Montanaro and Tobias J. Osborne. Quantum boolean functions. Chicago Journal of Theoretical Computer Science, 2010(1), January 2010.
- [32] Elchanan Mossel, Ryan O’Donnell, and Krzysztof Oleszkiewicz. Noise stability of functions with low influences: Invariance and optimality. Annals of Mathematics, 171:295–341, Mar 2010.
- [33] A. Natarajan and J. Wright. NEEXP is contained in MIP. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 510–518, Los Alamitos, CA, USA, nov 2019. IEEE Computer Society.
- [34] Michael A Nielsen and Isaac L Chuang. Quantum computation and quantum information. Cambridge University Press, Cambridge, UK, 2000.
- [35] Ryan O’Donnell. Analysis of Boolean Functions. Cambridge University Press, Cambridge, UK, 2013.
- [36] Minglong Qin and Penghui Yao. Nonlocal games with noisy maximally entangled states are decidable. SIAM Journal on Computing, 50(6):1800–1891, 2021.
- [37] Oded Regev and Thomas Vidick. Quantum XOR games. ACM Trans. Comput. Theory, 7(4), aug 2015.
- [38] Cambyse Roué, Melchior Wirth, and Haonan Zhang. Quantum talagrand, kkl and friedgut’s theorems and the learnability of quantum boolean functions. arXiv preprint arXiv:2209.07279, 2209.07279.
- [39] C. J. Stark and A. W. Harrow. Compressibility of positive semidefinite factorizations and quantum models. IEEE Transactions on Information Theory, 62(5):2867–2880, 2016.
- [40] Dave Touchette. Quantum information complexity. In Proceedings of the Forty-seventh Annual ACM Symposium on Theory of Computing, STOC ’15, pages 317–326, New York, NY, USA, 2015. ACM.
- [41] Guoming Wang. Property testing of unitary operators. Phys. Rev. A, 84:052328, Nov 2011.
- [42] John Watrous. Theory of Quantum Information. Cambridge University Press, Cambridge, UK, 2018.
- [43] Pingping Zhang. On some inequalities related to positive block matrices. Linear Algebra and its Applications, 576:258–267, 2019.