Related papers: Four Related Combinatorial Problems

Four Related Combinatorial Problems

URL: http://arxiv.org/abs/2311.07716v1
Date: Mon, 13 Nov 2023 19:57:12 GMT
Title: Four Related Combinatorial Problems
Authors: Stan Gudder
Abstract summary: We show that a quantum measure $mu$ satisfies a grade-2 additivity condition. We then show that this solves the original quantum measure problem.
Score: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: This pedagogical article solves an interesting problem in quantum measure theory. Although a quantum measure $\mu$ is a generalization of an ordinary probability measure, $\mu$ need not satisfy the usual additivity condition. Instead, $\mu$ satisfies a grade-2 additivity condition. Besides the quantum measure problem, we present three additional combinatorial problems. These are (1)\enspace A sum of binomial coefficients problem;\enspace (2)\enspace A recurrence relation problem; and\enspace (3)\enspace An interated vector problem. We show that these three problems are equivalent in that they have a common solution. We then show that this solves the original quantum measure problem.

Related papers

Explicit Solution Equation for Every Combinatorial Problem via Tensor Networks: MeLoCoToN [55.2480439325792]
We show that every computation problem has an exact explicit equation that returns its solution. We present a method to obtain an equation that solves exactly any problem, both inversion, constraint satisfaction and optimization.
arXiv Detail & Related papers (2025-02-09T18:16:53Z)
A QUBO Formulation for the Generalized LinkedIn Queens and Takuzu/Tango Game [49.1574468325115]
We present a QUBO formulation designed to solve a series of generalisations of the LinkedIn queens game. We adapt this formulation for several particular cases of the problem, as Tents & Trees. We also present two new types of problems, the Coloured Chess Piece Problem and the Max Chess Pieces Problem, with their corresponding QUBO formulations.
arXiv Detail & Related papers (2024-10-08T23:54:54Z)
A hybrid Quantum proposal to deal with 3-SAT problem [75.38606213726906]
This paper presents and describes a hybrid quantum computing strategy for solving 3-SAT problems. The performance of this approximation has been tested over a set of representative scenarios when dealing with 3-SAT from the quantum computing perspective.
arXiv Detail & Related papers (2023-06-07T12:19:22Z)
Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
arXiv Detail & Related papers (2022-12-06T22:01:49Z)
What does it take to solve the measurement problem? [0.0]
We show that no current interpretation of quantum mechanics solves the measurement problem. We speculate what a solution of the measurement problem might be good for.
arXiv Detail & Related papers (2022-06-21T14:49:42Z)
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)
On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids [63.75363908696257]
The lackadaisical quantum walk is an algorithm developed to search graph structures whose vertices have a self-loop of weight $l$. This paper addresses several issues related to applying the lackadaisical quantum walk to search for multiple solutions on grids successfully.
arXiv Detail & Related papers (2021-06-11T09:43:09Z)
Limits of quantum speed-ups for computational geometry and other problems: Fine-grained complexity via quantum walks [0.0]
We prove optimal lower-bounds on the time complexity of quantum algorithms for several computational problems. Most of our lower-bounds are optimal, in that they match known upper-bounds, and hence they imply tight limits on the quantum speedup.
arXiv Detail & Related papers (2021-06-03T17:22:08Z)
Quantum Constraint Problems can be complete for $\mathsf{BQP}$, $\mathsf{QCMA}$, and more [0.0]
We show that all quantum constraint problems can be realized on qubits, a trait not shared with classical constraint problems. Results suggest a significant diversity of classes present in quantum constraint problems.
arXiv Detail & Related papers (2021-01-21T01:08:04Z)
Quantum algorithm of a set of quantum 2-sat problem [0.0]
We present a quantum adiabatic algorithm for a set of quantum 2-satisfiability (Q2SAT) problem. For a Q2SAT problem, we construct the Hamiltonian which is similar to that of a Heisenberg chain.
arXiv Detail & Related papers (2020-09-05T21:01:27Z)

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