Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2311.07716

Four Related Combinatorial Problems

Stanley Gudder

Published Nov 13, 2023• 0 citations
arXivHTMLPDF

Abstract

This pedagogical article solves an interesting problem in quantum measure theory. Although a quantum measure $μ$ is a generalization of an ordinary probability measure, $μ$ need not satisfy the usual additivity condition. Instead, $μ$ 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.

DOI
10.48550/arxiv.2311.07716

Related papers

Finite Quantum Measure Spaces

Stanley Gudder

Quantum measure spaces possess a certain “quantum weirdness” and lack some of the simplicity and intuitive nature of their classical counterparts. Much of this unusual behavior is due to a phenomenon called quantum interference, which is a recurrent theme in the present article. Because of this interference, quantum measures need not be additive but satisfy a more general condition called grade-2 additivity. Examples of quantum measure spaces such as “quantum coins” and particle-an tip article pairs are considered. Even more general spaces called super-quantum measure spaces are discussed. You don't need quantum mechanics or measure theory to understand this article.

American Mathematical Monthly•Jan 1, 2010•16 citations

Generalized phase-matching condition for nondegenerate four-wave mixing

Phillip R. Peterson, A. Gavrielides, David A. Cardimona

The coupled-probe, conjugate, and pump differential equations are solved in the undepleted pump approximation when the pumps are of unequal frequencies. In the usual analysis the two pump wave vectors satisfy k1 + k2 = 0, so that the conjugate and probe wave vectors satisfy kp + kc = 0. The vector phase matching then consists of two one-dimensional problems. However, the unequal pump frequencies require a true two-dimensional analysis, since the pump wave vectors do not sum to zero separately from the probe/conjugate fields. This then requires the inclusion of a transverse dimension in the differential equations. The net result is that the direction of the maximum conjugate intensity, usually determined by the phase-match condition Δk = 0, is instead determined by the generalized condition kc · Δk = 0, where Δk = k1 + k2 − kp − kc. This new phase-matching condition is quadratic in kc, leading to two peaks in the conjugate reflection coefficient.

Journal of the Optical Society of America B•Mar 1, 1987•3 citations

SOME IDENTITIES FOR THE QUANTUM MEASURE AND ITS GENERALIZATIONS

Roberto B. Salgado

After a brief review of classical probability theory (measure theory), we present an observation (due to Sorkin) concerning an aspect of probability in quantum mechanics. Following Sorkin, we introduce a generalized measure theory based on a hierarchy of "sum-rules". The first sum-rule yields classical probability theory, and the second yields a generalized probability theory that includes quantum mechanics as a special case. We present some algebraic relations involving these sum-rules. This may be useful for the study of the higher-order sum-rules and possible generalizations of quantum mechanics. We conclude with some open questions and suggestions for further work.

arXiv:gr-qc/9903015•Modern Physics Letters A•Apr 20, 2002•33 citations

Some Identities for the Quantum Measure and its Generalizations

Salgado, R B

After a brief review of classical probability theory (measure theory), we present an observation (due to Sorkin) concerning an aspect of probability in quantum mechanics. Following Sorkin, we introduce a generalized measure theory based on a hierarchy of ``sum-rules.'' The first sum-rule yields classical probability theory, and the second yields a generalized probability theory that includes quantum mechanics as a special case. We present some algebraic relations involving these sum-rules. This may be useful for the study of the higher-order sum-rules and possible generalizations of quantum mechanics. We conclude with some open questions and suggestions for further work.

•Mar 10, 1999•40 citations

Rounding Sum-of-Squares Relaxations

Boaz Barak, Jonathan A. Kelner, David Steurer

We present a general approach to rounding semidefinite programming relaxations obtained by the Sum-of-Squares method (Lasserre hierarchy). Our approach is based on using the connection between these relaxations and the Sum-of-Squares proof system to transform a *combining algorithm* -- an algorithm that maps a distribution over solutions into a (possibly weaker) solution -- into a *rounding algorithm* that maps a solution of the relaxation to a solution of the original problem. Using this approach, we obtain algorithms that yield improved results for natural variants of three well-known problems: 1) We give a quasipolynomial-time algorithm that approximates the maximum of a low degree multivariate polynomial with non-negative coefficients over the Euclidean unit sphere. Beyond being of interest in its own right, this is related to an open question in quantum information theory, and our techniques have already led to improved results in this area (Brandão and Harrow, STOC '13). 2) We give a polynomial-time algorithm that, given a d dimensional subspace of R^n that (almost) contains the characteristic function of a set of size n/k, finds a vector $v$ in the subspace satisfying $|v|_4^4 > c(k/d^{1/3}) |v|_2^2$, where $|v|_p = (E_i v_i^p)^{1/p}$. Aside from being a natural relaxation, this is also motivated by a connection to the Small Set Expansion problem shown by Barak et al. (STOC 2012) and our results yield a certain improvement for that problem. 3) We use this notion of L_4 vs. L_2 sparsity to obtain a polynomial-time algorithm with substantially improved guarantees for recovering a planted $μ$-sparse vector v in a random d-dimensional subspace of R^n. If v has mu n nonzero coordinates, we can recover it with high probability whenever $μ< O(\min(1,n/d^2))$, improving for $d < n^{2/3}$ prior methods which intrinsically required $μ< O(1/\sqrt(d))$.

arXiv:1312.6652•Electronic colloquium on computational complexity•Dec 23, 2013•0 citations

Seven combinatorial equations in quantum computation

AN Xue-mei

Seven combinatorial equations posed by a scientist in quantum combination are proved in this paper.

Journal of Southwest University•Jan 1, 2005•0 citations
This pedagogical article solves an interesting problem in quantum measure theory. Although a quantum measure μμμ is a generalization of an ordinary probability measure, μμμ need not satisfy the usual additivity condition. Instead, μμμ 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.
Quantum measure spaces possess a certain “quantum weirdness” and lack some of the simplicity and intuitive nature of their classical counterparts. Much of this unusual behavior is due to a phenomenon called quantum interference, which is a recurrent theme in the present article. Because of this interference, quantum measures need not be additive but satisfy a more general condition called grade-2 additivity. Examples of quantum measure spaces such as “quantum coins” and particle-an tip article pairs are considered. Even more general spaces called super-quantum measure spaces are discussed. You don't need quantum mechanics or measure theory to understand this article.
The coupled-probe, conjugate, and pump differential equations are solved in the undepleted pump approximation when the pumps are of unequal frequencies. In the usual analysis the two pump wave vectors satisfy k1 + k2 = 0, so that the conjugate and probe wave vectors satisfy kp + kc = 0. The vector phase matching then consists of two one-dimensional problems. However, the unequal pump frequencies require a true two-dimensional analysis, since the pump wave vectors do not sum to zero separately from the probe/conjugate fields. This then requires the inclusion of a transverse dimension in the differential equations. The net result is that the direction of the maximum conjugate intensity, usually determined by the phase-match condition Δk = 0, is instead determined by the generalized condition kc · Δk = 0, where Δk = k1 + k2 − kp − kc. This new phase-matching condition is quadratic in kc, leading to two peaks in the conjugate reflection coefficient.
After a brief review of classical probability theory (measure theory), we present an observation (due to Sorkin) concerning an aspect of probability in quantum mechanics. Following Sorkin, we introduce a generalized measure theory based on a hierarchy of "sum-rules". The first sum-rule yields classical probability theory, and the second yields a generalized probability theory that includes quantum mechanics as a special case. We present some algebraic relations involving these sum-rules. This may be useful for the study of the higher-order sum-rules and possible generalizations of quantum mechanics. We conclude with some open questions and suggestions for further work.
After a brief review of classical probability theory (measure theory), we present an observation (due to Sorkin) concerning an aspect of probability in quantum mechanics. Following Sorkin, we introduce a generalized measure theory based on a hierarchy of ``sum-rules.'' The first sum-rule yields classical probability theory, and the second yields a generalized probability theory that includes quantum mechanics as a special case. We present some algebraic relations involving these sum-rules. This may be useful for the study of the higher-order sum-rules and possible generalizations of quantum mechanics. We conclude with some open questions and suggestions for further work.
We present a general approach to rounding semidefinite programming relaxations obtained by the Sum-of-Squares method (Lasserre hierarchy). Our approach is based on using the connection between these relaxations and the Sum-of-Squares proof system to transform a *combining algorithm* -- an algorithm that maps a distribution over solutions into a (possibly weaker) solution -- into a *rounding algorithm* that maps a solution of the relaxation to a solution of the original problem. Using this approach, we obtain algorithms that yield improved results for natural variants of three well-known problems: 1) We give a quasipolynomial-time algorithm that approximates the maximum of a low degree multivariate polynomial with non-negative coefficients over the Euclidean unit sphere. Beyond being of interest in its own right, this is related to an open question in quantum information theory, and our techniques have already led to improved results in this area (Brandão and Harrow, STOC '13). 2) We give a polynomial-time algorithm that, given a d dimensional subspace of R^n that (almost) contains the characteristic function of a set of size n/k, finds a vector vvv in the subspace satisfying ∣v∣44>c(k/d1/3)∣v∣22|v|_4^4 > c(k/d^{1/3}) |v|_2^2∣v∣44​>c(k/d1/3)∣v∣22​, where ∣v∣p=(Eivip)1/p|v|_p = (E_i v_i^p)^{1/p}∣v∣p​=(Ei​vip​)1/p. Aside from being a natural relaxation, this is also motivated by a connection to the Small Set Expansion problem shown by Barak et al. (STOC 2012) and our results yield a certain improvement for that problem. 3) We use this notion of L_4 vs. L_2 sparsity to obtain a polynomial-time algorithm with substantially improved guarantees for recovering a planted μμμ-sparse vector v in a random d-dimensional subspace of R^n. If v has mu n nonzero coordinates, we can recover it with high probability whenever μ<O(min⁡(1,n/d2))μ< O(\min(1,n/d^2))μ<O(min(1,n/d2)), improving for d<n2/3d < n^{2/3}d<n2/3 prior methods which intrinsically required μ<O(1/(d))μ< O(1/\sqrt(d))μ<O(1/(​d)).