Quantum Computational Complexity and Symmetry

• URL: http://arxiv.org/abs/2309.10081v1
• Date: Mon, 18 Sep 2023 18:48:44 GMT
• Title: Quantum Computational Complexity and Symmetry
• Authors: Soorya Rethinasamy, Margarite L. LaBorde, Mark M. Wilde
• Abstract summary: Testing the symmetries of quantum states and channels provides a way to assess their usefulness. We prove that various symmetry-testing problems are complete for BQP, QMA, QSZK, QIP(2), QIP_EB(2), and QIP. We also prove the inclusion of two Hamiltonian symmetry-testing problems in QMA and QAM.
• Score: 3.9134031118910264
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Testing the symmetries of quantum states and channels provides a way to assess their usefulness for different physical, computational, and communication tasks. Here, we establish several complexity-theoretic results that classify the difficulty of symmetry-testing problems involving a unitary representation of a group and a state or a channel that is being tested. In particular, we prove that various such symmetry-testing problems are complete for BQP, QMA, QSZK, QIP(2), QIP_EB(2), and QIP, thus spanning the prominent classes of the quantum interactive proof hierarchy and forging a non-trivial connection between symmetry and quantum computational complexity. Finally, we prove the inclusion of two Hamiltonian symmetry-testing problems in QMA and QAM, while leaving it as an intriguing open question to determine whether these problems are complete for these classes.

Related papers

• QuanTest: Entanglement-Guided Testing of Quantum Neural Network Systems [45.18451374144537]
  Quantum Neural Network (QNN) combines the Deep Learning (DL) principle with the fundamental theory of quantum mechanics to achieve machine learning tasks with quantum acceleration. QNN systems differ significantly from traditional quantum software and classical DL systems, posing critical challenges for QNN testing. We propose QuanTest, a quantum entanglement-guided adversarial testing framework to uncover potential erroneous behaviors in QNN systems.
  arXiv  Detail & Related papers  (2024-02-20T12:11:28Z)
• A Menagerie of Symmetry Testing Quantum Algorithms [0.0]
  We show how to generate a notion of symmetry from a discrete, finite group and how this generalizes to a continuous group. We propose quantum algorithms capable of testing whether a Hamiltonian exhibits symmetry with respect to a group. We prove that the acceptance probability of each algorithm is equal to the maximum symmetric fidelity of the state being tested.
  arXiv  Detail & Related papers  (2023-05-23T22:55:02Z)
• Quantum Imitation Learning [74.15588381240795]
  We propose quantum imitation learning (QIL) with a hope to utilize quantum advantage to speed up IL. We develop two QIL algorithms, quantum behavioural cloning (Q-BC) and quantum generative adversarial imitation learning (Q-GAIL) Experiment results demonstrate that both Q-BC and Q-GAIL can achieve comparable performance compared to classical counterparts.
  arXiv  Detail & Related papers  (2023-04-04T12:47:35Z)
• Unitary property testing lower bounds by polynomials [0.15229257192293197]
  We study unitary property testing, where a quantum algorithm is given query access to a black-box unitary. Characterizing the complexity of these problems requires new algorithmic techniques and lower bound methods. We present a unitary property testing-based approach towards an oracle separation between $mathsfQMA$ and $mathsfQMA(2)$.
  arXiv  Detail & Related papers  (2022-10-12T03:01:00Z)
• Symmetric Pruning in Quantum Neural Networks [111.438286016951]
  Quantum neural networks (QNNs) exert the power of modern quantum machines. QNNs with handcraft symmetric ansatzes generally experience better trainability than those with asymmetric ansatzes. We propose the effective quantum neural tangent kernel (EQNTK) to quantify the convergence of QNNs towards the global optima.
  arXiv  Detail & Related papers  (2022-08-30T08:17:55Z)
• Quantum Algorithms for Testing Hamiltonian Symmetry [4.62316736194615]
  We show that familiar expressions of Hamiltonian symmetry in quantum mechanics correspond directly with the acceptance of our algorithms. We execute one of our symmetry-testing algorithms on existing quantum computers for simple examples of both symmetric and asymmetric cases.
  arXiv  Detail & Related papers  (2022-03-18T15:30:50Z)
• Approximate symmetries and quantum error correction [0.6526824510982799]
  Quantum error correction (QEC) is a key concept in quantum computation as well as many areas of physics. We study the competition between continuous symmetries and QEC in a quantitative manner. We showcase two explicit types of quantum codes, obtained from quantum Reed--Muller codes and thermodynamic codes, that nearly saturate our bounds.
  arXiv  Detail & Related papers  (2021-11-11T18:09:33Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard. We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware. The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
  arXiv  Detail & Related papers  (2021-07-08T17:59:55Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP) This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm. Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
  arXiv  Detail & Related papers  (2021-05-06T17:59:38Z)
• Sampling Overhead Analysis of Quantum Error Mitigation: Uncoded vs. Coded Systems [69.33243249411113]
  We show that Pauli errors incur the lowest sampling overhead among a large class of realistic quantum channels. We conceive a scheme amalgamating QEM with quantum channel coding, and analyse its sampling overhead reduction compared to pure QEM.
  arXiv  Detail & Related papers  (2020-12-15T15:51:27Z)
• Supersymmetry and Quantum Computation [0.0]
  The interplay between supersymmetry and classical and quantum computation is discussed. Concrete examples, including the supersymmetric SYK model and fermion hard-core models are discussed.
  arXiv  Detail & Related papers  (2020-11-02T19:00:01Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.