The mixedness of one share of a pure bipartite state determines whether the overall state is a separable, unentangled one. Here we consider quantum computational tests of mixedness, and we derive an exact expression of the acceptance probability of such tests as the number of copies of the state becomes larger. We prove that the analytical form of this expression is given by the cycle index polynomial of the symmetric group S k , which is itself related to the Bell polynomials. After doing so, we derive a family of quantum separability tests, each of which is generated by a finite group; for all such algorithms, we show that the acceptance probability is determined by the cycle index polynomial of the group. Finally, we produce and analyse explicit circuit constructions for these tests, showing that the tests corresponding to the symmetric and cyclic groups can be executed with O ( k 2 ) and O ( k log ( k ) ) controlled-SWAP gates, respectively, where k is the number of copies of the state being tested.
The mixedness of one share of a pure bipartite state determines whether the overall state is a separable, unentangled one. Here we consider quantum computational tests of mixedness, and we derive an exact expression of the acceptance probability of such tests as the number of copies of the state becomes larger. We prove that the analytical form of this expression is given by the cycle index polynomial of the symmetric group S k , which is itself related to the Bell polynomials. After doing so, we derive a family of quantum separability tests, each of which is generated by a finite group; for all such algorithms, we show that the acceptance probability is determined by the cycle index polynomial of the group. Finally, we produce and analyse explicit circuit constructions for these tests, showing that the tests corresponding to the symmetric and cyclic groups can be executed with O ( k 2 ) and O ( k log ( k ) ) controlled-SWAP gates, respectively, where k is the number of copies of the state being tested.
In Chapter 1, we establish the mathematical background used throughout this thesis. We review concepts from group and representation theory. We further establish fundamental concepts from quantum information. This will allow us to then define the different notions of symmetry necessary in the following chapters. In Chapter 2, we investigate Hamiltonian symmetries. We propose quantum algorithms capable of testing whether a Hamiltonian exhibits symmetry with respect to a group. Furthermore, we show that this algorithm is that this algorithm is DQC1-Complete. Finally, we execute one of our symmetry-testing algorithms on existing quantum computers for simple examples. In Chapter 3, we discuss tests of symmetry for quantum states. For the case of testing Bose symmetry of a state, there is a simple and efficient quantum algorithm, while the tests for other kinds of symmetry rely on the aid of a quantum prover. We prove that the acceptance probability of each algorithm is equal to the maximum symmetric fidelity of the state being tested Finally, we establish various generalizations of the resource theory of asymmetry, with the upshot being that the acceptance probabilities of the algorithms are resource monotones. In Chapter 4, we begin by showing that the analytical form of the acceptance probability of such a test is given by the cycle index polynomial of the symmetric group ���� . We derive a family of quantum separability tests, each of which is generated by a finite group; for all such algorithms, we show that the acceptance probability is determined by the cycle index polynomial of the group. Finally, we produce and analyze explicit circuit constructions for these tests, showing that the tests corresponding to the symmetric and cyclic groups can be executed with ��(��2) and ��(�� log(��)) controlled-SWAP gates, respectively, where �� is the number of copies of the state In Chapter 5, we include additional results not previously published; in particular, we give a test for symmetry of a quantum state using density matrix exponentiation, a further result of Hamiltonian symmetry measurements when using Abelian groups, and an alternate Hamiltonian symmetry test construction for a block-encoded Hamiltonian.
Abstract Quantum entanglement is essential to the development of quantum computation, communications, and technology. The controlled SWAP test, widely used for state comparison, can be adapted to an efficient and useful test for entanglement of a pure state. Here we show that the test can evidence the presence of entanglement (and further, genuine n-qubit entanglement), can distinguish entanglement classes, and that the concurrence of a two-qubit state is related to the test’s output probabilities. We also propose a multipartite measure of entanglement that acts similarly for n-qubit states. The average number of copies of the test state required to detect entanglement decreases for larger systems, to four on average for many (n ≳ 8) qubits for maximally entangled states. For non-maximally entangled states, the number of copies required to detect entanglement increases with decreasing entanglement. Furthermore, the results are robust to second order when typical small errors are introduced to the state under investigation.
To determine whether a given multipartite quantum state is separable with respect to some partition, we construct a family of entanglement measures {Rm(ρ)}. This is done utilizing generalized concurrences as building blocks which are defined by flipping of M constituents and indicate states that are separable with regard to bipartitions when vanishing. Furthermore, we provide an analytically computable lower bound for {Rm(ρ)} via a simple ordering relation of the convex roof extension. Using the derived lower bound, we illustrate the effect of the isotropic noise on a family of four-qubit mixed states for each intermediate separability.
Suppose that a polynomial-time mixed-state quantum circuit, described as a sequence of local unitary interactions followed by a partial trace, generates a quantum state shared between two parties. One might then wonder, does this quantum circuit produce a state that is separable or entangled? Here, we give evidence that it is computationally hard to decide the answer to this question, even if one has access to the power of quantum computation. We begin by exhibiting a two-message quantum interactive proof system that can decide the answer to a promise version of the question. We then prove that the promise problem is hard for the class of promise problems with "quantum statistical zero knowledge" (QSZK) proof systems by demonstrating a polynomial-time Karp reduction from the QSZK-complete promise problem "quantum state distinguish ability" to our quantum separability problem. By exploiting Knill's efficient encoding of a matrix description of a state into a description of a circuit to generate the state, we can show that our promise problem is NP-hard with respect to Cook reductions. Thus, the quantum separability problem (as phrased above) constitutes the first nontrivial promise problem decidable by a two-message quantum interactive proof system while being hard for both NP and QSZK. We also consider a variant of the problem, in which a given polynomial-time mixed-state quantum circuit accepts a quantum state as input, and the question is to decide if there is an input to this circuit which makes its output separable across some bipartite cut. We prove that this problem is a complete promise problem for the class QIP of problems decidable by quantum interactive proof systems. Finally, we show that a two-message quantum interactive proof system can also decide a multipartite generalization of the quantum separability problem.
Pure-state consistency problems naturally lead to quantum proof systems in which a single pure witness must satisfy many acceptance constraints. The corresponding class PureSuperQMA was previously known to lie between QMA and QMA(2), and Kamminga and Rudolph (ITCS'26) conjectured that both containments are strict. In this paper, we prove the following surprising complexity collapses QMA=PureSuperQMA=PureSuperQMA(exp)=BellPureSymQMA(poly) Here PureSuperQMA(exp) allows exponentially many checks which are uniformly indexed and efficiently generated, while requiring an inverse-polynomial violation margin and an inverse-polynomial fraction of violated checks for the NO cases. BellPureSymQMA(poly) is a related model that requires the prover to give the verifier polynomially many copies of a pure state, which the verifier measures separately with logarithmic output length for each local measurement, before processing the outcomes jointly.
The main technical ingredient is a dimension-free stability bound for symmetric tensor states. Our simulations use polynomially many witness registers and combine a random-pair SWAP test with a permutation-invariant lift of the original verification procedure. The key step is to show that, on the symmetric subspace, the extremal verification value is close to that of some tensor-power witness with dimension-independent error. Applying this argument to the two verification models yields both simulations. As a consequence, exact k-local pure-state consistency is QMA-complete for every fixed k≥2, and so are the corresponding exact bosonic and fermionic pure N-representability problems.
Suppose that a polynomial-time mixed-state quantum circuit, described as a sequence of local unitary interactions followed by a partial trace, generates a quantum state shared between two parties. One might then wonder, does this quantum circuit produce a state that is separable or entangled? Here, we give evidence that it is computationally hard to decide the answer to this question, even if one has access to the power of quantum computation. We begin by exhibiting a two-message quantum interactive proof system that can decide the answer to a promise version of the question. We then prove that the promise problem is hard for the class of promise problems with "quantum statistical zero knowledge" QSZK proof systems by demonstrating a polynomial-time Karp reduction from the QSZK-complete promise problem "quantum state distinguishability" to our quantum separability problem. By exploiting Knill's efficient encoding of a matrix description of a state into a description of a circuit to generate the state, we can show that our promise problem is NP-hard with respect to Cook reductions. Thus, the quantum separability problem (as phrased above) constitutes the first nontrivial promise problem decidable by a two-message quantum interactive proof system while being hard for both NP and QSZK. We also consider a variant of the problem, in which a given polynomial-time mixed-state quantum circuit accepts a quantum state as input, and the question is to decide if there is an input to this circuit which makes its output separable across some bipartite cut. We prove that this problem is a complete promise problem for the class QIP of problems decidable by quantum interactive proof systems. Finally, we show that a two-message quantum interactive proof system can also decide a multipartite generalization of the quantum separability problem.