Quantum State Synthesis: Relation with Decision Complexity Classes and Impossibility of Synthesis Error Reduction

• URL: http://arxiv.org/abs/2407.02907v2
• Date: Fri, 30 Aug 2024 13:25:00 GMT
• Title: Quantum State Synthesis: Relation with Decision Complexity Classes and Impossibility of Synthesis Error Reduction
• Authors: Hugo Delavenne, François Le Gall,
• Abstract summary: This work investigates the relationships between quantum state synthesis complexity classes and traditional decision complexity classes. We especially investigate the role of the synthesis error parameter, which characterizes the quality of the synthesis in quantum state synthesis complexity classes.
• Score: 0.3376269351435395
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This work investigates the relationships between quantum state synthesis complexity classes (a recent concept in computational complexity that focuses on the complexity of preparing quantum states) and traditional decision complexity classes. We especially investigate the role of the synthesis error parameter, which characterizes the quality of the synthesis in quantum state synthesis complexity classes. We first show that in the high synthesis error regime, collapse of synthesis classes implies collapse of the equivalent decision classes. For more reasonable synthesis error, we then show a similar relationships for BQP and QCMA. Finally, we show that for quantum state synthesis classes it is in general impossible to improve the quality of the synthesis: unlike the completeness and soundness parameters (which can be improved via repetition), the synthesis error cannot be reduced, even with arbitrary computational power.

Related papers

• SynthesizRR: Generating Diverse Datasets with Retrieval Augmentation [55.2480439325792]
  We study the synthesis of six datasets, covering topic classification, sentiment analysis, tone detection, and humor. We find that SynthesizRR greatly improves lexical and semantic diversity, similarity to human-written text, and distillation performance.
  arXiv  Detail & Related papers  (2024-05-16T12:22:41Z)
• ExeDec: Execution Decomposition for Compositional Generalization in Neural Program Synthesis [54.18659323181771]
  We characterize several different forms of compositional generalization that are desirable in program synthesis. We propose ExeDec, a novel decomposition-based strategy that predicts execution subgoals to solve problems step-by-step informed by program execution at each step.
  arXiv  Detail & Related papers  (2023-07-26T01:07:52Z)
• Compositional Generalization and Decomposition in Neural Program Synthesis [59.356261137313275]
  In this paper, we focus on measuring the ability of learned program synthesizers to compositionally generalize. We first characterize several different axes along which program synthesis methods would be desired to generalize. We introduce a benchmark suite of tasks to assess these abilities based on two popular existing datasets.
  arXiv  Detail & Related papers  (2022-04-07T22:16:05Z)
• Too Big to Fail? Active Few-Shot Learning Guided Logic Synthesis [18.961915757370466]
  We propose Bulls-Eye, that fine-tunes a pre-trained model on past synthesis data to accurately predict the quality of a synthesis recipe for an unseen netlist. This approach achieves 2x-10x run-time improvement and better quality-of-result (QoR) than state-of-the-art machine learning approaches.
  arXiv  Detail & Related papers  (2022-04-05T17:18:04Z)
• Quantum Parameterized Complexity [1.01129133945787]
  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.
  arXiv  Detail & Related papers  (2022-03-15T15:34:38Z)
• Interactive Proofs for Synthesizing Quantum States and Unitaries [0.15229257192293197]
  We study the complexity of inherently quantum operations such as constructing quantum states or performing unitary transformations. We define models of interactive proofs for quantum states and unitaries. We obtain analogous results in the setting with multiple entangled provers as well.
  arXiv  Detail & Related papers  (2021-08-16T15:59:33Z)
• Satisfiability and Synthesis Modulo Oracles [7.246701762489972]
  Many synthesis algorithms use a white-box oracle based on satisfiability modulo theory (SMT) solvers to provide counterexamples. We present a framework for solving a general class of oracle-guided synthesis problems which we term synthesis modulo oracles. We also formalize the problem of satisfiability modulo theories and oracles, and present an algorithm for solving this problem.
  arXiv  Detail & Related papers  (2021-07-28T16:36:26Z)
• Latent Execution for Neural Program Synthesis Beyond Domain-Specific Languages [97.58968222942173]
  We take the first step to synthesize C programs from input-output examples. In particular, we propose La Synth, which learns the latent representation to approximate the execution of partially generated programs. We show that training on these synthesized programs further improves the prediction performance for both Karel and C program synthesis.
  arXiv  Detail & Related papers  (2021-06-29T02:21:32Z)
• 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)
• RetroXpert: Decompose Retrosynthesis Prediction like a Chemist [60.463900712314754]
  We devise a novel template-free algorithm for automatic retrosynthetic expansion. Our method disassembles retrosynthesis into two steps. While outperforming the state-of-the-art baselines, our model also provides chemically reasonable interpretation.
  arXiv  Detail & Related papers  (2020-11-04T04:35:34Z)
• Towards Neural-Guided Program Synthesis for Linear Temporal Logic Specifications [26.547133495699093]
  We use a neural network to learn a Q-function that is then used to guide search, and to construct programs that are subsequently verified for correctness. Our method is unique in combining search with deep learning to realize synthesis.
  arXiv  Detail & Related papers  (2019-12-31T17:09:49Z)

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.