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:quant-ph/9712053

A diakoptic approach to quantum computation

Giuseppe Castagnoli, Dalida Monti

Published Dec 23, 1997• 0 citations
arXivHTMLPDF

Abstract

In the diakoptic approach, mechanisms are divided into simpler parts interconnected in some standard way (say by a "mechanical connection''). We explore the possibility of applying this approach to quantum mechanisms: the specialties of the quantum domain seem to yield a richer result. First parts are made independent of each other by assuming that connections are removed. The overall state would thus become a superposition of tensor products of the eigenstates of the independent parts. Connections are restored by projecting off all the tensor products which violate them. This would be performed by particle statistics, under a special interpretation thereof. The NP-complete problem of testing the satisfiability of a Boolean network is approached in this way. The diakoptic approach appears to be able of taming the quantum whole without clipping its richness.

DOI
10.48550/arxiv.quant-ph/9712053

Related papers

A reductionistic approach to quantum computation

Giuseppe Castagnoli, Dalida Monti

In the reductionistic approach, mechanisms are divided into simpler parts interconnected in some standard way (e.g. by a mechanical transmission). We explore the possibility of porting reductionism in quantum operations. Conceptually, first parts are made independent of each other by assuming that all ``transmissions'' are removed. The overall state would thus become a superposition of tensor products of the eigenstates of the independent parts. Transmissions are restored by projecting off all the tensor products which violate them. This would be performed by particle statistics; the plausibility of this scheme is based on the interpretation of particle statistics as projection. The problem of the satisfiability of a Boolean network is approached in this way. This form of quantum reductionism appears to be able of taming the quantum whole without clipping its richness.

arXiv:quant-ph/9711045•Nov 20, 1997•0 citations

Exploiting Particle Statistics in Quantum Computation

Giuseppe Castagnoli, Dalida Monti

We describe a plausible-speculative form of quantum computation which exploits particle (fermionic, bosonic) statistics, under a generalized, counterfactual interpretation thereof. In the idealized situation of an isolated system, it seems that this form of computation yields to NP-complete=P.

arXiv:quant-ph/9806086•Jun 25, 1998•0 citations

Quantum Nondeterministic Computation based on Statistics Superselection Rules

Giuseppe Castagnoli

Quantum states which obey certain symmetry superselection rules under identical particles permutation can be interpreted as computational states satisfying corresponding Boolean predicates. Given the NP-complete problem of testing the satisfiability of a generic Boolean predicate P, we investigate the possibility of achieving quantum nondeterministic computation by deriving, from P, a physical situation in which the computational states satisfy Piff they satisfy a special fermion statistics.

International Journal of Modern Physics B•Apr 20, 1997•1 citation

Quantum Computation and the Evaluation of Tensor Networks

Itai Arad, Zeph A. Landau

We present a quantum algorithm that additively approximates the value of a tensor network to a certain scale. When combined with existing results, this provides a complete problem for quantum computation. The result is a simple new way of looking at quantum computation in which unitary gates are replaced by tensors and time is replaced by the order in which the tensor network is “swallowed.” We use this result to derive new quantum algorithms that approximate the partition function of a variety of classical statistical mechanical models, including the Potts model.

arXiv:0805.0040•SIAM Journal on Computing•Jan 1, 2010•70 citations

Tensor Network Rewriting Strategies for Satisfiability and Counting

Niel de Beaudrap, Aleks Kissinger, Konstantinos Meichanetzidis

We provide a graphical treatment of SAT and #SAT on equal footing. Instances of #SAT can be represented as tensor networks in a standard way. These tensor networks are interpreted by diagrams of the ZH-calculus: a system to reason about tensors over C in terms of diagrams built from simple generators, in which computation may be carried out by transformations of diagrams alone. In general, nodes of ZH diagrams take parameters over C which determine the tensor coefficients; for the standard representation of #SAT instances, the coefficients take the value 0 or 1. Then, by choosing the coefficients of a diagram to range over B, we represent the corresponding instance of SAT. Thus, by interpreting a diagram either over the boolean semiring or the complex numbers, we instantiate either the decision or counting version of the problem. We find that for classes known to be in P, such as 2SAT and #XORSAT, the existence of appropriate rewrite rules allows for efficient simplification of the diagram, producing the solution in polynomial time. In contrast, for classes known to be NP-complete, such as 3SAT, or #P-complete, such as #2SAT, the corresponding rewrite rules introduce hyperedges to the diagrams, in numbers which are not easily bounded above by a polynomial. This diagrammatic approach unifies the diagnosis of the complexity of CSPs and #CSPs and shows promise in aiding tensor network contraction-based algorithms.

arXiv:2004.06455•Electronic Proceedings in Theoretical Computer Science•Sep 6, 2021•15 citations

Does Quantum Mechanics Require “Conspiracy”?

Ovidiu Cristinel Stoica

Quantum states containing records of incompatible outcomes of quantum measurements are valid states in the tensor-product Hilbert space. Since they contain false records, they conflict with the Born rule and with our observations. I show that excluding them requires a fine-tuning to an extremely restricted subspace of the Hilbert space that seems "conspiratorial", in the sense that (1) it seems to depend on future events that involve records (including measurement settings) and on the dynamical law (normally thought to be independent of the initial conditions), and (2) it violates Statistical Independence, even when it is valid in the context of Bell's theorem. To solve the puzzle, I build a model in which, by changing the dynamical law, the same initial conditions can lead to different histories in which the validity of records is relative to the new dynamical law. This relative validity of the records may restore causality, but the initial conditions still must depend, at least partially, on the dynamical law. While violations of Statistical Independence are often seen as non-scientific, they turn out to be needed to ensure the validity of records and our own memories and, by this, of science itself. A Past Hypothesis is needed to ensure the existence of records and turns out to require violations of Statistical Independence. It is not excluded that its explanation, still unknown, ensures such violations in the way needed by local interpretations of quantum mechanics. I suggest that an as-yet unknown law or superselection rule may restrict the full tensor-product Hilbert space to the very special subspace required by the validity of records and the Past Hypothesis.

arXiv:2209.13275•Entropy•May 9, 2024•3 citations
In the diakoptic approach, mechanisms are divided into simpler parts interconnected in some standard way (say by a "mechanical connection''). We explore the possibility of applying this approach to quantum mechanisms: the specialties of the quantum domain seem to yield a richer result. First parts are made independent of each other by assuming that connections are removed. The overall state would thus become a superposition of tensor products of the eigenstates of the independent parts. Connections are restored by projecting off all the tensor products which violate them. This would be performed by particle statistics, under a special interpretation thereof. The NP-complete problem of testing the satisfiability of a Boolean network is approached in this way. The diakoptic approach appears to be able of taming the quantum whole without clipping its richness.
In the reductionistic approach, mechanisms are divided into simpler parts interconnected in some standard way (e.g. by a mechanical transmission). We explore the possibility of porting reductionism in quantum operations. Conceptually, first parts are made independent of each other by assuming that all ``transmissions'' are removed. The overall state would thus become a superposition of tensor products of the eigenstates of the independent parts. Transmissions are restored by projecting off all the tensor products which violate them. This would be performed by particle statistics; the plausibility of this scheme is based on the interpretation of particle statistics as projection. The problem of the satisfiability of a Boolean network is approached in this way. This form of quantum reductionism appears to be able of taming the quantum whole without clipping its richness.
We present a quantum algorithm that additively approximates the value of a tensor network to a certain scale. When combined with existing results, this provides a complete problem for quantum computation. The result is a simple new way of looking at quantum computation in which unitary gates are replaced by tensors and time is replaced by the order in which the tensor network is “swallowed.” We use this result to derive new quantum algorithms that approximate the partition function of a variety of classical statistical mechanical models, including the Potts model.
We provide a graphical treatment of SAT and #SAT on equal footing. Instances of #SAT can be represented as tensor networks in a standard way. These tensor networks are interpreted by diagrams of the ZH-calculus: a system to reason about tensors over C in terms of diagrams built from simple generators, in which computation may be carried out by transformations of diagrams alone. In general, nodes of ZH diagrams take parameters over C which determine the tensor coefficients; for the standard representation of #SAT instances, the coefficients take the value 0 or 1. Then, by choosing the coefficients of a diagram to range over B, we represent the corresponding instance of SAT. Thus, by interpreting a diagram either over the boolean semiring or the complex numbers, we instantiate either the decision or counting version of the problem. We find that for classes known to be in P, such as 2SAT and #XORSAT, the existence of appropriate rewrite rules allows for efficient simplification of the diagram, producing the solution in polynomial time. In contrast, for classes known to be NP-complete, such as 3SAT, or #P-complete, such as #2SAT, the corresponding rewrite rules introduce hyperedges to the diagrams, in numbers which are not easily bounded above by a polynomial. This diagrammatic approach unifies the diagnosis of the complexity of CSPs and #CSPs and shows promise in aiding tensor network contraction-based algorithms.
Quantum states containing records of incompatible outcomes of quantum measurements are valid states in the tensor-product Hilbert space. Since they contain false records, they conflict with the Born rule and with our observations. I show that excluding them requires a fine-tuning to an extremely restricted subspace of the Hilbert space that seems "conspiratorial", in the sense that (1) it seems to depend on future events that involve records (including measurement settings) and on the dynamical law (normally thought to be independent of the initial conditions), and (2) it violates Statistical Independence, even when it is valid in the context of Bell's theorem. To solve the puzzle, I build a model in which, by changing the dynamical law, the same initial conditions can lead to different histories in which the validity of records is relative to the new dynamical law. This relative validity of the records may restore causality, but the initial conditions still must depend, at least partially, on the dynamical law. While violations of Statistical Independence are often seen as non-scientific, they turn out to be needed to ensure the validity of records and our own memories and, by this, of science itself. A Past Hypothesis is needed to ensure the existence of records and turns out to require violations of Statistical Independence. It is not excluded that its explanation, still unknown, ensures such violations in the way needed by local interpretations of quantum mechanics. I suggest that an as-yet unknown law or superselection rule may restrict the full tensor-product Hilbert space to the very special subspace required by the validity of records and the Past Hypothesis.