Quantum Parameterized Complexity

• URL: http://arxiv.org/abs/2203.08002v1
• Date: Tue, 15 Mar 2022 15:34:38 GMT
• Title: Quantum Parameterized Complexity
• Authors: Michael J. Bremner, Zhengfeng Ji, Ryan L. Mann, Luke Mathieson, Mauro E.S. Morales, Alexis T.E. Shaw
• Abstract summary: We introduce the quantum analogues of a range of parameterized complexity classes. This framework exposes a rich classification of the complexity of parameterized versions of QMA-hard problems.
• Score: 1.01129133945787
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Parameterized complexity theory was developed in the 1990s to enrich the complexity-theoretic analysis of problems that depend on a range of parameters. In this paper we establish a quantum equivalent of classical parameterized complexity theory, motivated by the need for new tools for the classifications of the complexity of real-world problems. We introduce the quantum analogues of a range of parameterized complexity classes and examine the relationship between these classes, their classical counterparts, and well-studied problems. This framework exposes a rich classification of the complexity of parameterized versions of QMA-hard problems, demonstrating, for example, a clear separation between the Quantum Circuit Satisfiability problem and the Local Hamiltonian problem.

Related papers

• Benchmarking quantum chaos from geometric complexity [0.23436632098950458]
  We consider a new method to study geometric complexity for interacting non-Gaussian quantum mechanical systems. Within some limitations, geometric complexity can indeed be a good indicator of quantum chaos.
  arXiv  Detail & Related papers  (2024-10-24T14:04:58Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties? We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d. We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• Taming Quantum Time Complexity [45.867051459785976]
  We show how to achieve both exactness and thriftiness in the setting of time complexity. We employ a novel approach to the design of quantum algorithms based on what we call transducers.
  arXiv  Detail & Related papers  (2023-11-27T14:45:19Z)
• Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
  The anticipated applications of quantum computers span across science and industry. We present a survey of several potential application areas of quantum algorithms. We outline the challenges and opportunities in each area in an "end-to-end" fashion.
  arXiv  Detail & Related papers  (2023-10-04T17:53:55Z)
• Unitary Complexity and the Uhlmann Transformation Problem [41.67228730328207]
  We introduce a framework for unitary synthesis problems, including notions of reductions and unitary complexity classes. We use this framework to study the complexity of transforming one entangled state into another via local operations. Our framework for unitary complexity thus provides new avenues for studying the computational complexity of many natural quantum information processing tasks.
  arXiv  Detail & Related papers  (2023-06-22T17:46:39Z)
• The Quantum Path Kernel: a Generalized Quantum Neural Tangent Kernel for Deep Quantum Machine Learning [52.77024349608834]
  Building a quantum analog of classical deep neural networks represents a fundamental challenge in quantum computing. Key issue is how to address the inherent non-linearity of classical deep learning. We introduce the Quantum Path Kernel, a formulation of quantum machine learning capable of replicating those aspects of deep machine learning.
  arXiv  Detail & Related papers  (2022-12-22T16:06:24Z)
• Tunable Complexity Benchmarks for Evaluating Physics-Informed Neural Networks on Coupled Ordinary Differential Equations [64.78260098263489]
  In this work, we assess the ability of physics-informed neural networks (PINNs) to solve increasingly-complex coupled ordinary differential equations (ODEs) We show that PINNs eventually fail to produce correct solutions to these benchmarks as their complexity increases. We identify several reasons why this may be the case, including insufficient network capacity, poor conditioning of the ODEs, and high local curvature, as measured by the Laplacian of the PINN loss.
  arXiv  Detail & Related papers  (2022-10-14T15:01:32Z)
• Clique Homology is QMA1-hard [0.0]
  We show that the decision problem of determining homology groups of simplicial complexes is QMA1-hard. This suggests that the seemingly classical problem may in fact be quantum mechanical. We discuss potential implications for the problem of quantum advantage in topological data analysis.
  arXiv  Detail & Related papers  (2022-09-23T18:14:16Z)
• Open Problems Related to Quantum Query Complexity [4.467248776406005]
  I offer a case that quantum query complexity still has loads of enticing and fundamental open problems. I offer a case that quantum query complexity still has loads of enticing and fundamental open problems.
  arXiv  Detail & Related papers  (2021-09-14T18:36:15Z)
• Detailed Account of Complexity for Implementation of Some Gate-Based Quantum Algorithms [55.41644538483948]
  In particular, some steps of the implementation, as state preparation and readout processes, can surpass the complexity aspects of the algorithm itself. We present the complexity involved in the full implementation of quantum algorithms for solving linear systems of equations and linear system of differential equations.
  arXiv  Detail & Related papers  (2021-06-23T16:33:33Z)
• Aspects of The First Law of Complexity [0.0]
  We investigate the first law of complexity proposed in arXiv:1903.04511, i.e., the variation of complexity when the target state is perturbed. Based on Nielsen's geometric approach to quantum circuit complexity, we find the variation only depends on the end of the optimal circuit.
  arXiv  Detail & Related papers  (2020-02-13T21:15:57Z)

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.