Toward Entailment Checking: Explore Eigenmarking Search

• URL: http://arxiv.org/abs/2506.03771v1
• Date: Wed, 04 Jun 2025 09:33:10 GMT
• Title: Toward Entailment Checking: Explore Eigenmarking Search
• Authors: Tatpong Katanyukul,
• Abstract summary: quantum computing may allow an effective approach for various problems, including entailment checking.<n> Grover algorithm uses Grover operations, selective phase inversion and amplitude amplification to address a search over unstructured data.<n>Our study explores various schemes of eigenmarking'' approach.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Logic entailment is essential to reasoning, but entailment checking has the worst-case complexity of an exponential of the variable size. With recent development, quantum computing when mature may allow an effective approach for various combinatorial problems, including entailment checking. Grover algorithm uses Grover operations, selective phase inversion and amplitude amplification to address a search over unstructured data with quadratic improvement from a classical method. Its original form is intended to a single-winner scenario: exactly one match is promised. Its extension to multiple-winner cases employs probabilistic control over a number of applications of Grover operations, while a no-winner case is handled by time-out. Our study explores various schemes of ``eigenmarking'' approach. Still relying on Grover operations, but the approach introduces additional qubits to tag the eigenstates. The tagged eigenstates are to facilitate an interpretation of the measured results and enhance identification of a no-winner case (related to no logic violation in entailment context). Our investigation experiments three variations of eigenmarking on a two-qubit system using an IBM Aer simulator. The results show strong distinguishability in all schemes with the best relative distinguishabilities of 19 and 53 in worst case and in average case, respectively. Our findings reveal a viable quantum mechanism to differentiate a no-winner case from other scenarios, which could play a pivot role in entailment checking and logic reasoning in general.

Related papers

• Critical Thinking: Which Kinds of Complexity Govern Optimal Reasoning Length? [72.70486097967124]
  We formalize a framework using deterministic finite automata (DFAs)<n>We show that there exists an optimal amount of reasoning tokens such that the probability of producing a correct solution is maximized.<n>We then demonstrate an implication of these findings: being able to predict the optimal number of reasoning tokens for new problems and filtering out non-optimal length answers results in consistent accuracy improvements.
  arXiv  Detail & Related papers  (2025-04-02T17:45:58Z)
• Robustness of different modifications of Grovers algorithm based on generalized Householder reflections with different phases [0.0]
  We study five Grovers algorithm modifications, where each iteration is constructed by two generalized Householder reflections. By using semi-empirical methods, we investigate various characteristics of the dependence between the probability to find solution and the phase errors.
  arXiv  Detail & Related papers  (2024-01-07T23:04:39Z)
• Majorization-based benchmark of the complexity of quantum processors [105.54048699217668]
  We numerically simulate and characterize the operation of various quantum processors. We identify and assess quantum complexity by comparing the performance of each device against benchmark lines. We find that the majorization-based benchmark holds as long as the circuits' output states have, on average, high purity.
  arXiv  Detail & Related papers  (2023-04-10T23:01:10Z)
• Non-Exponential Behaviour in Logical Randomized Benchmarking [0.0]
  We construct a gate and time-independent noise model that results in the output of a logical randomized benchmarking protocol. We show that the presence of machinery associated with the implementation of quantum error correction can facilitate non-exponential decay.
  arXiv  Detail & Related papers  (2022-12-11T12:30:27Z)
• Nested Counterfactual Identification from Arbitrary Surrogate Experiments [95.48089725859298]
  We study the identification of nested counterfactuals from an arbitrary combination of observations and experiments. Specifically, we prove the counterfactual unnesting theorem (CUT), which allows one to map arbitrary nested counterfactuals to unnested ones.
  arXiv  Detail & Related papers  (2021-07-07T12:51:04Z)
• Tractable Inference in Credal Sentential Decision Diagrams [116.6516175350871]
  Probabilistic sentential decision diagrams are logic circuits where the inputs of disjunctive gates are annotated by probability values. We develop the credal sentential decision diagrams, a generalisation of their probabilistic counterpart that allows for replacing the local probabilities with credal sets of mass functions. For a first empirical validation, we consider a simple application based on noisy seven-segment display images.
  arXiv  Detail & Related papers  (2020-08-19T16:04:34Z)
• Optimizing Quantum Search with a Binomial Version of Grover's Algorithm [4.220030262107688]
  Amplitude Amplification -- a key component of Grover's Search algorithm -- uses an iterative approach to systematically increase the probability of one or multiple target states. We present novel strategies to enhance the amplification procedure by partitioning the states into classes.
  arXiv  Detail & Related papers  (2020-07-21T15:36:35Z)
• Quantile Multi-Armed Bandits: Optimal Best-Arm Identification and a Differentially Private Scheme [16.1694012177079]
  We study the best-arm identification problem in multi-armed bandits with, potentially private rewards. The goal is to identify the arm with the highest quantile at a fixed, prescribed level. We show that our algorithm is $delta$-PAC and we characterize its sample complexity.
  arXiv  Detail & Related papers  (2020-06-11T20:23:43Z)
• The Price of Incentivizing Exploration: A Characterization via Thompson Sampling and Sample Complexity [83.81297078039836]
  We consider incentivized exploration: a version of multi-armed bandits where the choice of arms is controlled by self-interested agents. We focus on the price of incentives: the loss in performance, broadly construed, incurred for the sake of incentive-compatibility.
  arXiv  Detail & Related papers  (2020-02-03T04:58:51Z)
• Best Arm Identification for Cascading Bandits in the Fixed Confidence Setting [81.70513857417106]
  We design and analyze CascadeBAI, an algorithm for finding the best set of $K$ items. An upper bound on the time complexity of CascadeBAI is derived by overcoming a crucial analytical challenge. We show, through the derivation of a lower bound on the time complexity, that the performance of CascadeBAI is optimal in some practical regimes.
  arXiv  Detail & Related papers  (2020-01-23T16:47:52Z)

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.