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:1709.05430 · Physical Review A

Arbitrarily exhaustive hypergraph generation of 4-, 6-, 8-, 16-, and 32-dimensional quantum contextual sets

Mladen Pavičić

Published Jun 26, 2017• 14 citations
arXivHTMLPDF

Abstract

Quantum contextuality turns out to be a necessary resource for universal quantum computation and important in the field of quantum information processing. It is therefore of interest both for theoretical considerations and for experimental implementation to find new types and instances of contextual sets and develop methods of their optimal generation. We present an arbitrarily exhaustive hypergraph-based generation of the most explored contextual sets [Kochen-Specker (KS) ones] in 4, 6, 8, 16, and 32 dimensions. We consider and analyze 12 KS classes and obtain numerous properties of theirs, which we then compare with the results previously obtained in the literature. We generate several thousand additional types and instances of KS sets, including all KS sets in three of the classes and the upper part of a fourth set. We make use of the McKay-Megill-Pavi\ifmmode \check{c}\else \v{c}\fi{}i\ifmmode \acute{c}\else \'{c}\fi{} (MMP) hypergraph language, algorithms, and programs to generate KS sets strictly following their definition from the Kochen-Specker theorem. This approach proves to be particularly advantageous over the parity-proof-based ones (which prevail in the literature) since it turns out that only a very few KS sets have a parity proof (in six KS classes 0.01% and in one of them 0%). MMP hypergraph formalism enables a translation of an exponentially complex task of solving systems of nonlinear equations, describing KS vector orthogonalities, into a statistically linearly complex task of evaluating vertex states of hypergraph edges, thus exponentially speeding up the generation of KS sets and enabling us to generate billions of novel instances of them. The MMP hypergraph notation also enables us to graphically represent KS sets and to visually discern their features.

DOI
10.1103/physreva.95.062121

Related papers

Vector generation of contextual sets

Mladen Pavičić, Norman D. Megill

\nAs quantum contextuality proves to be a necessary resource for universal quantum computation, we present a general method for vector generation of Kochen-Specker (KS) contextual sets in the form of hypergraphs. The method supersedes all three previous methods: (i) fortuitous discoveries of smallest KS sets, (ii) exhaustive upward hypergraph-generation of sets, and (iii) random downward generation of sets from fortuitously obtained big master sets. In contrast to previous works, we can generate master sets which contain all possible KS sets starting with nothing but a few simple vector components. From them we can readily generate all KS sets obtained in the last half a century and any specified new KS sets. Herewith we can generate sufficiently large sets as well as sets with definite required features and structures to enable varieties of different implementations in quantum computation and communication.\n

•Jan 15, 2019•2 citations

Vector generation of contextual sets

Mladen Pavičić, Norman D. Megill

As quantum contextuality proves to be a necessary resource for universal quantum computation, we present a general method for vector generation of Kochen-Specker (KS) contextual sets in the form of hypergraphs. The method supersedes all three previous methods: (i) fortuitous discoveries of smallest KS sets, (ii) exhaustive upward hypergraph-generation of sets, and (iii) random downward generation of sets from fortuitously obtained big master sets. In contrast to previous works, we can generate master sets which contain all possible KS sets starting with nothing but a few simple vector components. From them we can readily generate all KS sets obtained in the last half a century and any specified new KS sets. Herewith we can generate sufficiently large sets as well as sets with definite required features and structures to enable varieties of different implementations in quantum computation and communication.

arXiv:1905.01784•EPJ Web of Conferences•Jan 1, 2019•3 citations

Vector Generation of Quantum Contextual Sets in Even Dimensional Hilbert Spaces

Mladen Pavičić, Norman D. Megill

Recently, quantum contextuality has been proved to be the source of quantum computation's power. That, together with multiple recent contextual experiments, prompts improving the methods of generation of contextual sets and finding their features. The most elaborated contextual sets, which offer blueprints for contextual experiments and computational gates, are the Kochen-Specker (KS) sets. In this paper, we show a method of vector generation that supersedes previous methods. It is implemented by means of algorithms and programs that generate hypergraphs embodying the Kochen-Specker property and that are designed to be carried out on supercomputers. We show that vector component generation of KS hypergraphs exhausts all possible vectors that can be constructed from chosen vector components, in contrast to previous studies that used incomplete lists of vectors and therefore missed a majority of hypergraphs. Consequently, this unified method is far more efficient for generations of KS sets and their implementation in quantum computation and quantum communication. Several new KS classes and their features have been found and are elaborated on in the paper. Greechie diagrams are discussed.

arXiv:1905.01567•Entropy•Dec 5, 2018•19 citations

Automated generation of Kochen-Specker sets

Mladen Pavičić, Mordecai Waegell, Norman D. Megill +1 more

Quantum contextuality turns out to be a necessary resource for universal quantum computation and also has applications in quantum communication. Thus it becomes important to generate contextual sets of arbitrary structure and complexity to enable a variety of implementations. In recent years, such generation has been done for contextual sets known as Kochen-Specker sets. Up to now, two approaches have been used for massive generation of non-isomorphic Kochen-Specker sets: exhaustive generation up to a given size and downward generation from master sets and their associated coordinatizations. Master sets were obtained earlier from serendipitous or intuitive connections with polytopes or Pauli operators, and more recently from arbitrary vector components using an algorithm that generates orthogonal vector groupings from them. However, both upward and downward generation face an inherent exponential complexity barrier. In contrast, in this paper we present methods and algorithms that we apply to downward generation that can overcome the exponential barrier in many cases of interest. These involve tailoring and manipulating Kochen-Specker master sets obtained from a small number of simple vector components, filtered by the features of the sets we aim to obtain. Some of the classes of Kochen-Specker sets we generate contain all previously known ones, and others are completely novel. We provide examples of both kinds in 4- and 6-dim Hilbert spaces. We also give a brief introduction for a wider audience and a novice reader.

arXiv:1905.01009•Scientific Reports•May 1, 2019•10 citations

Generation of Kochen-Specker contextual sets in higher dimensions by dimensional upscaling whose complexity does not scale with dimension and their applications

Mladen Pavičić, Mordecai Waegell

Recently, handling of contextual sets, in particular Kochen-Specker (KS) sets, in higher dimensions has been given an increasing attention, both theoretically and experimentally. However, methods of their generation are diverse, not generally applicable in every dimension, and of exponential complexity. Therefore, we design a dimensional upscaling method, whose complexity does not scale with dimension. As a proof of principle we generate manageable-sized KS master sets in up to 27 dimensional spaces and show that well over 32 dimensions can be reached. From these master sets we obtain an ample number of smaller KS sets. We discuss three kinds of applications that work with KS sets in higher dimensions. We anticipate other applications of KS sets for quantum information processing that make use of large families of nonisomorphic KS sets.

arXiv:2305.08267•Physical Review A•Jul 3, 2024•4 citations

Non-Kochen–Specker Contextuality

Mladen Pavičić

Quantum contextuality supports quantum computation and communication. One of its main vehicles is hypergraphs. The most elaborated are the Kochen-Specker ones, but there is also another class of contextual sets that are not of this kind. Their representation has been mostly operator-based and limited to special constructs in three- to six-dim spaces, a notable example of which is the Yu-Oh set. Previously, we showed that hypergraphs underlie all of them, and in this paper, we give general methods-whose complexity does not scale up with the dimension-for generating such non-Kochen-Specker hypergraphs in any dimension and give examples in up to 16-dim spaces. Our automated generation is probabilistic and random, but the statistics of accumulated data enable one to filter out sets with the required size and structure.

arXiv:2307.16339•Entropy•Jul 26, 2023•3 citations
Quantum contextuality turns out to be a necessary resource for universal quantum computation and important in the field of quantum information processing. It is therefore of interest both for theoretical considerations and for experimental implementation to find new types and instances of contextual sets and develop methods of their optimal generation. We present an arbitrarily exhaustive hypergraph-based generation of the most explored contextual sets [Kochen-Specker (KS) ones] in 4, 6, 8, 16, and 32 dimensions. We consider and analyze 12 KS classes and obtain numerous properties of theirs, which we then compare with the results previously obtained in the literature. We generate several thousand additional types and instances of KS sets, including all KS sets in three of the classes and the upper part of a fourth set. We make use of the McKay-Megill-Pavi\ifmmode \check{c}\else \v{c}\fi{}i\ifmmode \acute{c}\else '{c}\fi{} (MMP) hypergraph language, algorithms, and programs to generate KS sets strictly following their definition from the Kochen-Specker theorem. This approach proves to be particularly advantageous over the parity-proof-based ones (which prevail in the literature) since it turns out that only a very few KS sets have a parity proof (in six KS classes 0.01% and in one of them 0%). MMP hypergraph formalism enables a translation of an exponentially complex task of solving systems of nonlinear equations, describing KS vector orthogonalities, into a statistically linearly complex task of evaluating vertex states of hypergraph edges, thus exponentially speeding up the generation of KS sets and enabling us to generate billions of novel instances of them. The MMP hypergraph notation also enables us to graphically represent KS sets and to visually discern their features.
\nAs quantum contextuality proves to be a necessary resource for universal quantum computation, we present a general method for vector generation of Kochen-Specker (KS) contextual sets in the form of hypergraphs. The method supersedes all three previous methods: (i) fortuitous discoveries of smallest KS sets, (ii) exhaustive upward hypergraph-generation of sets, and (iii) random downward generation of sets from fortuitously obtained big master sets. In contrast to previous works, we can generate master sets which contain all possible KS sets starting with nothing but a few simple vector components. From them we can readily generate all KS sets obtained in the last half a century and any specified new KS sets. Herewith we can generate sufficiently large sets as well as sets with definite required features and structures to enable varieties of different implementations in quantum computation and communication.\n
As quantum contextuality proves to be a necessary resource for universal quantum computation, we present a general method for vector generation of Kochen-Specker (KS) contextual sets in the form of hypergraphs. The method supersedes all three previous methods: (i) fortuitous discoveries of smallest KS sets, (ii) exhaustive upward hypergraph-generation of sets, and (iii) random downward generation of sets from fortuitously obtained big master sets. In contrast to previous works, we can generate master sets which contain all possible KS sets starting with nothing but a few simple vector components. From them we can readily generate all KS sets obtained in the last half a century and any specified new KS sets. Herewith we can generate sufficiently large sets as well as sets with definite required features and structures to enable varieties of different implementations in quantum computation and communication.
Recently, quantum contextuality has been proved to be the source of quantum computation's power. That, together with multiple recent contextual experiments, prompts improving the methods of generation of contextual sets and finding their features. The most elaborated contextual sets, which offer blueprints for contextual experiments and computational gates, are the Kochen-Specker (KS) sets. In this paper, we show a method of vector generation that supersedes previous methods. It is implemented by means of algorithms and programs that generate hypergraphs embodying the Kochen-Specker property and that are designed to be carried out on supercomputers. We show that vector component generation of KS hypergraphs exhausts all possible vectors that can be constructed from chosen vector components, in contrast to previous studies that used incomplete lists of vectors and therefore missed a majority of hypergraphs. Consequently, this unified method is far more efficient for generations of KS sets and their implementation in quantum computation and quantum communication. Several new KS classes and their features have been found and are elaborated on in the paper. Greechie diagrams are discussed.
Quantum contextuality turns out to be a necessary resource for universal quantum computation and also has applications in quantum communication. Thus it becomes important to generate contextual sets of arbitrary structure and complexity to enable a variety of implementations. In recent years, such generation has been done for contextual sets known as Kochen-Specker sets. Up to now, two approaches have been used for massive generation of non-isomorphic Kochen-Specker sets: exhaustive generation up to a given size and downward generation from master sets and their associated coordinatizations. Master sets were obtained earlier from serendipitous or intuitive connections with polytopes or Pauli operators, and more recently from arbitrary vector components using an algorithm that generates orthogonal vector groupings from them. However, both upward and downward generation face an inherent exponential complexity barrier. In contrast, in this paper we present methods and algorithms that we apply to downward generation that can overcome the exponential barrier in many cases of interest. These involve tailoring and manipulating Kochen-Specker master sets obtained from a small number of simple vector components, filtered by the features of the sets we aim to obtain. Some of the classes of Kochen-Specker sets we generate contain all previously known ones, and others are completely novel. We provide examples of both kinds in 4- and 6-dim Hilbert spaces. We also give a brief introduction for a wider audience and a novice reader.
Recently, handling of contextual sets, in particular Kochen-Specker (KS) sets, in higher dimensions has been given an increasing attention, both theoretically and experimentally. However, methods of their generation are diverse, not generally applicable in every dimension, and of exponential complexity. Therefore, we design a dimensional upscaling method, whose complexity does not scale with dimension. As a proof of principle we generate manageable-sized KS master sets in up to 27 dimensional spaces and show that well over 32 dimensions can be reached. From these master sets we obtain an ample number of smaller KS sets. We discuss three kinds of applications that work with KS sets in higher dimensions. We anticipate other applications of KS sets for quantum information processing that make use of large families of nonisomorphic KS sets.
Quantum contextuality supports quantum computation and communication. One of its main vehicles is hypergraphs. The most elaborated are the Kochen-Specker ones, but there is also another class of contextual sets that are not of this kind. Their representation has been mostly operator-based and limited to special constructs in three- to six-dim spaces, a notable example of which is the Yu-Oh set. Previously, we showed that hypergraphs underlie all of them, and in this paper, we give general methods-whose complexity does not scale up with the dimension-for generating such non-Kochen-Specker hypergraphs in any dimension and give examples in up to 16-dim spaces. Our automated generation is probabilistic and random, but the statistics of accumulated data enable one to filter out sets with the required size and structure.