Pith. sign in

REVIEW 2 major objections 3 minor 1 cited by

Classical and Quantum Query Complexity of Boolean Functions under Indefinite Causal Order

T0 review · 2 major / 3 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper proves that causally indefinite computation—where operations are not bound to a fixed order—reduces classical query complexity polynomially and gives the first exact quantum query-complexity separation.

desk verdict Solid classical separation results and a clever quantum construction, but the quantum lower bound currently rests on an un-certified numerical SDP. read the letter →

arxiv 2506.05187 v2 pith:XQJEB2IE submitted 2025-06-05 quant-ph

Alastair A. Abbott , Mehdi Mhalla , Pierre Pocreau This is my paper
classification quant-ph MSC 68Q1281P68 PACS 03.67.Lx03.67.-a
keywords indefinitecausalorderquerycomplexityBooleanfunctionsdecisiontreesprocessquantumsupermapsexactpolynomialseparation
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper asks whether dropping the assumption that computations must run in a fixed order—allowing causally indefinite processes with no well-defined order among their operations—can reduce the number of queries needed to evaluate Boolean functions. It answers yes in two settings. For classical deterministic computation, it generalizes decision-tree complexity to process functions, proves that the degree and certificate lower bounds still hold, and constructs a 6-bit function $f_{6c}$ where causal indefiniteness saves one query; iterating that construction yields a polynomial separation. For quantum computation, it exhibits a 6-bit function $f_{6q}$ whose exact generalized query complexity is three while every sequential quantum algorithm needs four queries, giving the first exact quantum query-complexity separation from indefinite causal order. The paper also identifies why the quantum separation cannot yet be amplified to an asymptotic one: the causally indefinite supermap produces auxiliary registers that cannot be uncomputed without additional queries.

What carries the argument

The load-bearing object is the Lugano (AF/BW) process, a three-slot classical-deterministic process with induced functions $w_k(o_1,o_2,o_3) = (1 \oplus o_{k\oplus_3 1})o_{k\oplus_3 2}$, which violates every fixed causal order yet is logically consistent. The paper embeds it in the query model so that, at the unique fixed point, the three queries automatically target the 6-bit input pattern needed to evaluate $f_{6c}$, and it shows the same process, promoted to a quantum supermap and composed with one-query parity subroutines, evaluates $f_{6q}$. The amplification to a polynomial classical separation is carried by a recursive composition theorem showing $D_{\mathrm{Gen}}(f^{(l)}) \le D_{\mathrm{Gen}}(f)^l$, together with the standard composition rule $D(f^{(l)})=D(f)^l$ for decision trees. The quantum lower bound is carried by the semidefinite programming characterization of sequential exact query complexity, which reports a minimum error of about $0.0207$ for three-query computation of $f_{6q}$. The paper also identifies the barrier to further quantum amplification: the supermap is not clean, meaning its output register leaks information about the input beyond $f_{6q}(x)$.

What would settle it

Run the three-query sequential SDP for $f_{6q}$ in exact rational arithmetic or with a rigorously validated dual certificate and check whether the minimum error is truly positive, since a zero optimum would destroy the quantum separation. An explicit three-query quantum circuit computing $f_{6q}$ exactly on all 64 inputs would falsify the claimed lower bound directly.

Watch

Extended reading notes

Core claim

The central discovery is that causal indefiniteness is a genuine resource for query complexity, not merely for communication or discrimination tasks. The paper defines $D_{\mathrm{Gen}}(f)$ as the minimum number of queries needed when queries are wired together by an arbitrary classical-deterministic process, and proves that it lies between certificate complexity and decision-tree complexity: $C(f) \le D_{\mathrm{Gen}}(f) \le D(f) \le C(f)^2$. It then exhibits a 6-bit function $f_{6c}$ with $D_{\mathrm{Gen}}(f_{6c})=3 < D(f_{6c})=4$, and shows that recursive substitution of $f_{6c}$ into itself gives a family with $D_{\mathrm{Gen}}(f_{6c}^{(l)}) \le 3^l$ while $D(f_{6c}^{(l)})=4^l$, so $D_{\mathrm{Gen}} = O(D^{0.792\ldots})$. In the quantum setting it modifies the construction to $f_{6q}$ and proves $Q^{\mathrm{Gen}}_{E}(f_{6q})=3$ while $Q_{E}(f_{6q})=4$; the lower bound comes from solving a semidefinite program for the minimum error of any three-query sequential algorithm, and the upper bound is a causally indefinite quantum supermap built from the Lugano process together with one-query parity subroutines. This is, the paper contends, the first exact quantum query-complexity separation under indefinite causal order, while the classical separation shows the phenomenon is not inherently quantum.

Load-bearing premise

The claim that $f_{6q}$ cannot be computed with three sequential quantum queries rests on a numerical semidefinite-programming solution reporting a minimum error of about $\varepsilon_3^{\mathrm{Seq}}(f_{6q}) \approx 0.0207$, with no rigorous dual certificate; if the true optimum were zero, a three-query sequential algorithm would exist and the quantum separation would collapse.

Editorial extensions

If this is right

  • For every Boolean function $f$, $C(f) \le D_{\mathrm{Gen}}(f) \le D(f) \le C(f)^2$, so indefinite causal order can save at most a quadratic number of queries over ordinary decision trees.
  • The function $f_{6c}$ yields a constant separation, $D_{\mathrm{Gen}}(f_{6c})=3 < D(f_{6c})=4$, and the recursive family $\{f_{6c}^{(l)}\}_l$ gives a polynomial separation, $D_{\mathrm{Gen}}(f_{6c}^{(l)}) = O(D(f_{6c}^{(l)})^{0.792\ldots})$ with $D(f_{6c}^{(l)}) \to \infty$.
  • The function $f_{6q}$ yields $Q^{\mathrm{Gen}}_{E}(f_{6q})=3 < Q_{E}(f_{6q})=4$, the first exact quantum query-complexity separation attributable to indefinite causal order.
  • Because $\deg(f)/2 \le Q^{\mathrm{Gen}}_{E}(f) \le Q_{E}(f) \le \deg(f)^3$, only functions whose exact quantum complexity is well above half their degree can exhibit a separation, and $f_{6q}$ is such a function.
  • The quantum separation cannot currently be amplified by recursion because the supermap for $f_{6q}$ is not clean: the ancillary registers retain input information that would need uncomputing.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the semidefinite-programming lower bound for $f_{6q}$ is certified with an explicit dual solution, the quantum result becomes fully rigorous; until then, the classical polynomial separation is the rigorous headline achievement.
  • The Lugano process is the engine of both separations; a systematic search over other causally indefinite processes, especially with more than three slots, might yield larger constant separations and possibly approach the quadratic ceiling permitted by the certificate bounds.
  • The unclean-output barrier suggests a design principle: asymptotic quantum advantages from indefinite causal order will likely require constructions that erase their garbage naturally, or promise-based (partial) Boolean functions, where the paper notes super-polynomial advantages have not been ruled out.
  • Since $D_{\mathrm{Gen}}$ is polynomially related to both $D$ and $Q^{\mathrm{Gen}}_{E}$, the separation landscape is governed by the degree and certificate structure of the function; functions with a large gap between certificate complexity and decision-tree complexity are the natural candidates for further examples.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 3 minor

Summary. The paper introduces generalized query complexity frameworks for Boolean functions under indefinite causal order: a classical-deterministic model based on process functions and a quantum model based on general quantum supermaps. It proves that the standard degree and certificate lower bounds hold for the generalized classical query complexity DGen, constructs a 6-bit function f6c with DGen(f6c)=3 < D(f6c)=4, and amplifies this constant separation into a polynomial separation DGen(fl)=O(D(fl)^0.792) via recursive composition. In the quantum setting, it defines another 6-bit function f6q and claims an exact query complexity separation QGen_E(f6q)=3 < QE(f6q)=4, using a numerical SDP for the lower bound and a quantum version of the Lugano process for the upper bound. The classical results are supported by self-contained proofs; the quantum lower bound, however, rests on numerical evidence rather than a rigorous certificate.

Significance. If established rigorously, these results would be significant: they would provide the first exact query complexity separation between sequential and causally indefinite quantum computations in a standard oracle model, as well as a polynomial classical query advantage from indefinite causal order. The paper is careful in connecting its models to established process-function and quantum-supermap frameworks, and the classical constructions and proofs are explicit and reproducible. The public SDP code is a useful contribution. The central quantum claim, however, is currently not proven to the standard required for an exact-complexity theorem, because Proposition 13 depends on an unverified numerical SDP solution.

major comments (2)
  1. [Section 7.2; Proposition 13; Appendix D.1] The lower bound QE(f6q)=4, which is essential for Theorem 15, is not proved. The proof of Proposition 13 reports only a numerical solution of the SDP of Theorem 29, giving ε_3^Seq(f6q)≈0.0207 with primal/dual convergence to 1e-8. Appendix D.1 itself states that a rigorous lower bound would require extracting a certificate from the dual SDP. Since the separation in Theorem 15 collapses if the true SDP optimum were zero, this numerical evidence cannot support an exact-complexity theorem as stated. Please provide a rigorous dual certificate, a verified interval proving the optimum is positive, or an analytic argument; otherwise the quantum separation should be presented as conditional on numerical evidence.
  2. [Section 7.2.1; Appendix D.2] The upper bound QGen_E(f6q)=3 also needs a small formal gap filled: after the link product in Eq. (80), the text asserts that eW_f6q characterises a quantum supermap, but it does not explicitly verify that the composed matrix satisfies the required positivity and normalization constraints defining L_Gen, nor that each subroutine G_k is a valid one-slot quantum supermap. This is standard and likely follows from the circuit construction, but because it is the constructive side of the separation, an explicit statement of the relevant link-product rules would make the proof complete.
minor comments (3)
  1. [Theorem 15] The statement uses the symbol Q(f), but the paper elsewhere defines QE(f) and QGen_E(f); please define Q(f) or replace it with QE(f) for consistency.
  2. [Section 4.1] There is a duplicated word in the phrase 'the certificate complexity of of f' in the paragraph defining certificate complexity; please correct it.
  3. [Appendix D.1, footnote 8] Since the main text relies on the numerical value of ε_3^Seq(f6q), the footnote's remark that rigor would require extracting a dual certificate should also be reflected in the main text, not only in the appendix, so that readers are not misled about the status of Proposition 13.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: both separations rely on explicit constructions and external lower-bound tools; the numerical SDP proof gap is an exactness risk, not circularity.

full rationale

No circular steps were found. The classical separation is constructed explicitly: f6c is defined by Eq. (3), D(f6c)=4 is proved by an adversary-style decision-tree argument in Appendix B, and DGen(f6c)=3 is proved by giving a modified Lugano process and verifying its fixed points in Table 2; the lower bound also uses the independently proved certificate bound C(f6c)=3. Theorem 10 is proved directly from the definition of process functions, and the polynomial separation Theorem 11 follows by composition, with no fitted parameter. The quantum separation is likewise explicit: QGen_E(f6q)=3 is witnessed by the supermap eWf6q constructed in Appendix D.2 and verified in Table 4, and QE(f6q)=4 rests on the external SDP of Barnum, Saks and Szegedy [14] applied with T=3, not on a quantity fitted from the result being predicted. The authors' prior framework [5] supplies definitions and contextual bounds but not the separation, so its use is not load-bearing. The only flagged weakness is that Proposition 13 is numerical: Appendix D.1 states that epsilon_3^Seq(f6q) is approximately 0.0207, obtained with primal and dual converging and constraint violations below 10^-8, and the footnote explicitly says that to obtain a rigorous lower bound one could extract a certificate from the dual SDP. That is a proof-completeness and correctness risk, not a circularity, because the SDP input (the function f6q and T=3) is not definitionally equal to the claimed output QE(f6q)=4. Similarly, no step renames a known empirical pattern as a derivation, and no uniqueness theorem from the authors' own work is invoked to forbid alternatives.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The paper introduces no fitted free parameters and no new physical entities. Its central claims rest on prior formalism results, including the process-function fixed-point characterization, the causal separability equivalence, the SDP characterization of sequential quantum query complexity, and the decision tree composition theorem. The quantum lower bound additionally depends on a numerical SDP solution, which is not a formal proof.

assumptions (5)
  • domain assumption Unique fixed-point characterization of process functions, Proposition 2 from [19,18].
    This defines logical consistency for classical-deterministic processes and underlies the query model in Sections 3 and 4.
  • domain assumption The recursive definition of causally definite processes matches causal separability of classical process matrices.
    Appendix C.2 proves consistency with [43], and this equivalence justifies comparing decision trees with causally indefinite processes.
  • standard math The Barnum-Saks-Szegedy SDP exactly characterizes the minimum error of sequential T-query quantum algorithms.
    Theorem 29 from [14] is used in Appendix D.1 to conclude QE(f6q)=4 from the numerical value epsilon_3^Seq(f6q).
  • standard math The decision tree composition bound D(f^(l)) = T^l when D(f)=T, due to [37].
    This sets the baseline D(f6c^(l))=4^l in Section 6 against which DGen is compared.
  • domain assumption The Lugano process is logically consistent and causally indefinite, as established in [15,19].
    The Lugano process is the basis for the classical and quantum constructions in Sections 5, 6, and 7.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Classical and Quantum Query Complexity of Boolean Functions under Indefinite Causal Order." pith.science (2026). https://pith.science/paper/XQJEB2IE

@misc{pith2026250605187,
  author       = {Pith},
  title        = {Pith review of: Classical and Quantum Query Complexity of Boolean Functions under Indefinite Causal Order},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XQJEB2IE}},
  note         = {Machine review of arXiv:2506.05187}
}
read the original abstract

Computational models typically assume that operations are applied in a fixed sequential order. In recent years several works have looked at relaxing this assumption, considering computations without any fixed causal structure and showing that such ''causally indefinite'' computations can provide advantages in various tasks. Recently, the quantum query complexity of Boolean functions has been used as a tool to probe their computational power in a standard complexity theoretic framework, but no separation in exact query complexity has thus-far been found. In this paper, we investigate this problem starting with the simpler and fully classical notion of deterministic query complexity of Boolean functions, and using classical-deterministic processes -- which may exhibit causal indefiniteness -- as a generalised computational framework. We first show that the standard polynomial and certificate lower bounds of deterministic query complexity also hold in such generalised models. Then, we formulate a Boolean function for which causal indefiniteness permits a reduction in query complexity and show that this advantage can be amplified into a polynomial separation. Finally, with the insights gained in the classical-deterministic setting, we give a Boolean function whose quantum query complexity is reduced by causally indefinite computations.

Figures

Figures reproduced from arXiv: 2506.05187 by the authors.

Figure 1
Figure 1. Circuit diagram of the quantum subroutines [PITH_FULL_IMAGE:figures/full_fig_p011_1.png] view at source ↗
Figure 2
Figure 2. Circuit diagram of the quantum subroutines [PITH_FULL_IMAGE:figures/full_fig_p030_2.png] view at source ↗

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Routing Quantum Control of Causal Order

    quant-ph 2025-07 accept novelty 8.0 of 10

    Every N-party quantum circuit with quantum control of causal order can be represented as a routed quantum circuit built from one fixed routed graph G_QC-QC(N).

Reference graph

Works this paper leans on

47 extracted references · 15 canonical work pages · cited by 1 Pith paper

  1. [1]

    Version 10.1

    The MOSEK optimization toolbox for MATLAB manual. Version 10.1. https://www.mosek.com/

    work page

  2. [2]

    Quantum Info

    Scott Aaronson (2003): Quantum lower bound for recursive Fourier sampling. Quantum Info. Comput. 3(2), pp. 165–174, doi:10.26421/QIC5.2-9. arXiv:0209060

    work page doi:10.26421/qic5.2-9 2003

  3. [3]

    SIGACT News 36(1), pp

    Scott Aaronson (2005): Guest column: NP-complete problems and physical reality . SIGACT News 36(1), pp. 30–52, doi:10.1145/1052796.1052804. arXiv:0502072

    work page arXiv 2005

  4. [4]

    Scott Aaronson & John Watrous (2009): Closed timelike curves make quantum and classical computing equivalent. Proc. R. Soc. A: Math. Phys. Eng. Sci. 465(2102), pp. 631–647, doi:10.1098/rspa.2008.0350. arXiv:0808.2669

    work page arXiv 2009

  5. [5]

    Quantum Query Complexity of Boolean Functions under Indefinite Causal Order

    Alastair A. Abbott, Mehdi Mhalla & Pierre Pocreau (2024): Quantum query complexity of Boolean functions under indefinite causal order. Phys. Rev. Res. 6(3), p. L032020, doi:10.1103/PhysRevResearch.6.L032020. arXiv:2307.10285

    work page Pith review arXiv 2024

  6. [6]

    Andris Ambainis (2002): Quantum Lower Bounds by Quantum Arguments. J. Comput. Syst. Sci. 64(4), pp. 750–767, doi:10.1006/jcss.2002.1826. arXiv:quant-ph/0002066

    arXiv 2002

  7. [7]

    In: Proc

    Andris Ambainis (2013): Superlinear advantage for exact quantum algorithms. In: Proc. Annu. ACM Symp. Theory Comput., STOC ’13, ACM, Palo Alto, California, USA, pp. 891–900, doi:10.1145/2488608.2488721. arXiv:1211.0721

    work page arXiv 2013

  8. [8]

    In: Proc

    Andris Ambainis (2018): Understanding quantum algorithms via query complexity . In: Proc. Int. Congr. Math., ICM 2018, World Scientific, pp. 3265–3285, doi:10.1142/9789813272880_0181. arXiv:1712.06349

    arXiv 2018

Show all 47 references
  1. [9]

    Mateus Araújo, Cyril Branciard, Fabio Costa, Adrien Feix, Christina Giarmatzi & ˇCaslav Brukner (2015): Witnessing causal nonseparability. New J. Phys. 17(10), p. 102001, doi:10.1088/1367-2630/17/10/102001. arXiv:1506.03776

    2015 arXiv

  2. [10]

    Mateus Araújo, Fabio Costa & ˇCaslav Brukner (2014): Computational advantage from quantum- controlled ordering of gates . Phys. Rev. Lett. 113(25), p. 250402, doi:10.1103/PhysRevLett.113.250402. arXiv:1401.8127

    2014 arXiv

  3. [11]

    Quantum 1, p

    Mateus Araújo, Adrien Feix, Miguel Navascués & ˇCaslav Brukner (2017): A purification postulate for quantum mechanics with indefinite causal order . Quantum 1, p. 10, doi:10.22331/q-2017-04-26-10. arXiv:1611.08535

    2017 arXiv

  4. [12]

    Mateus Araújo, Philippe Allard Guérin & Ämin Baumeler (2017): Quantum computation with indefinite causal structures. Phys. Rev. A 96, p. 052315, doi:10.1103/PhysRevA.96.052315. arXiv:1706.09854

    2017 arXiv

  5. [13]

    Dave Bacon (2004): Quantum computational complexity in the presence of closed timelike curves . Phys. Rev. A 70(3), p. 032309, doi:10.1103/PhysRevA.70.032309. arXiv:0309189. A. A. Abbott, M. Mhalla & P. Pocreau 283

    2004 doi

  6. [14]

    In: Proc

    Howard Barnum, Michael Saks & Mario Szegedy (2003): Quantum query complexity and semi-definite programming. In: Proc. IEEE Annu. Conf. Comput. Complexity , CCC ’18, IEEE, pp. 179–193, doi:10.1109/CCC.2003.1214419

    2003 arXiv

  7. [15]

    Ämin Baumeler, Adrien Feix & Stefan Wolf (2014): Maximal incompatibility of locally classi- cal behavior and global causal order in multiparty scenarios . Phys. Rev. A 90(4), p. 042106, doi:10.1103/PhysRevA.90.042106. arXiv:1403.7333

    2014 arXiv

  8. [16]

    Quantum 6, p

    Ämin Baumeler, Amin Shiraz Gilani & Jibran Rashid (2022): Unlimited non-causal correlations and their relation to non-locality. Quantum 6, p. 673, doi:10.22331/q-2022-03-29-673. arXiv:2104.06234

    2022 arXiv

  9. [17]

    In: Proc

    Ämin Baumeler & Eleftherios Tselentis (2021): Equivalence of grandfather and information antinomy under intervention. In: Proc. 17th Int. Conf. Quantum Phys. Logic , QPL 2021, OPA, doi:10.4204/EPTCS.340.1. arXiv:2004.12921

    2021 arXiv

  10. [18]

    Ämin Baumeler & Stefan Wolf (2016): Device-independent test of causal order and relations to fixed-points. New J. Phys. 18(3), p. 035014, doi:10.1088/1367-2630/18/3/035014. arXiv:1511.05444

    2016 arXiv

  11. [19]

    Ämin Baumeler & Stefan Wolf (2016): The space of logically consistent classical processes without causal order. New J. Phys. 18(1), p. 013036, doi:10.1088/1367-2630/18/1/013036. arXiv:1507.01714

    2016 arXiv

  12. [20]

    Ämin Baumeler & Stefan Wolf (2018): Computational tameness of classical non-causal models . Proc. R. Soc. A: Math. Phys. Eng. Sci. 474(2209), p. 20170698, doi:10.1098/rspa.2017.0698. arXiv:1611.05641

    2018

  13. [21]

    Jessica Bavaresco, Mio Murao & Marco Túlio Quintino (2021): Strict hierarchy between parallel, sequen- tial, and indefinite-causal-order strategies for channel discrimination. Phys. Rev. Lett. 127(20), p. 200504, doi:10.1103/PhysRevLett.127.200504. arXiv:2011.08300

    2021 arXiv

  14. [22]

    Ethan Bernstein & Umesh Vazirani (1997): Quantum Complexity Theory . SIAM J. Comput. 26(5), pp. 1411–1473, doi:10.1137/S0097539796300921

    1997 doi

  15. [23]

    Brun (2003): Computers with closed timelike curves can solve hard problems efficiently

    Todd A. Brun (2003): Computers with closed timelike curves can solve hard problems efficiently . Found. Phys. Lett. 16, pp. 245–253, doi:10.1023/A:1025967225931. arXiv:0209061v1

    2003 doi

  16. [24]

    Harry Buhrman & Ronald de Wolf (2002): Complexity measures and decision tree complexity: a survey . Theor. Comput. Sci. 288(1), pp. 21–43, doi:10.1016/S0304-3975(01)00144-X

    2002 doi

  17. [25]

    Giulio Chiribella (2012): Perfect discrimination of no-signalling channels via quantum superposition of causal structures. Phys. Rev. A 86(4), p. 040301, doi:10.1103/PhysRevA.86.040301. arXiv:1109.5154

    2012 arXiv

  18. [26]

    Giulio Chiribella, Giacomo Mauro D’Ariano & Paolo Perinotti (2008): Quantum Circuit Architecture. Phys. Rev. Lett. 101(6), p. 060401, doi:10.1103/PhysRevLett.101.060401. arXiv:0712.1325

    2008 arXiv

  19. [27]

    Europhys

    Giulio Chiribella, Giacomo Mauro D’Ariano & Paolo Perinotti (2008): Transforming quantum operations: Quantum supermaps. Europhys. Lett. 83(3), p. 30004, doi:10.1209/0295-5075/83/30004. arXiv:0804.0180

    2008 arXiv

  20. [28]

    Giulio Chiribella, Giacomo Mauro D’Ariano & Paolo Perinotti (2009): Theoretical framework for quantum networks. Phys. Rev. A 80(2), p. 022339, doi:10.1103/PhysRevA.80.022339. arXiv:0904.4483

    2009 arXiv

  21. [29]

    Giulio Chiribella, Giacomo Mauro D’Ariano, Paolo Perinotti & Benoît Valiron (2013): Quantum computa- tions without definite causal structure . Phys. Rev. A 88(2), p. 022318, doi:10.1103/PhysRevA.88.022318. arXiv:0912.0195

    2013 arXiv

  22. [30]

    Linear Algebra Appl

    Man-Duen Choi (1975): Completely Positive Linear Maps on Complex Matrices . Linear Algebra Appl. 10(3), pp. 285–290, doi:10.1016/0024-3795(75)90075-0

    1975 doi

  23. [31]

    Richard Cleve, Artur Ekert, Chiara Macchiavello & Michele Mosca (1998): Quantum algorithms revisited. Proc. R. Soc. A 454(1969), pp. 339–354, doi:10.1098/rspa.1998.0164. arXiv:9708016

    1998

  24. [32]

    David Deutsch & Richard Jozsa (1992): Rapid solution of problems by quantum computation. Proc. R. Soc. A 439(1907), pp. 553–558, doi:10.1098/rspa.1992.0167

    1992

  25. [33]

    Philippe Allard Guérin, Adrien Feix, Mateus Araújo & ˇCaslav Brukner (2016): Exponential Communication Complexity Advantage from Quantum Superposition of the Direction of Communication . Phys. Rev. Lett. 117, p. 100502, doi:10.1103/PhysRevLett.117.100502. arXiv:1605.07372. 284...

    2016 arXiv

  26. [34]

    Andrzej Jamiołkowski (1972): Linear transformations which preserve trace and positive semidefiniteness of operators. Rep. Math. Phys. 3(4), pp. 275–278, doi:10.1016/0034-4877(72)90011-0

    1972 doi

  27. [35]

    arXiv:2409.18420

    Hlér Kristjánsson, Tatsuki Odake, Satoshi Yoshida, Philip Taranto, Jessica Bavaresco, Marco Túlio Quintino & Mio Murao (2024): Exponential separation in quantum query complexity of the quantum switch with respect to simulations with standard quantum circuits. arXiv:2409.18420

    2024 arXiv

  28. [36]

    In: 2004 Proc

    Johan Löfberg (2004): YALMIP: a toolbox for modeling and optimization in MATLAB. In: 2004 Proc. IEEE Int. Conf. Robot. Autom., ICRA 2004, IEEE, pp. 284–289, doi:10.1109/CACSD.2004.1393890

    2004 arXiv

  29. [37]

    Chicago J

    Ashley Montanaro (2014): A composition theorem for decision tree complexity. Chicago J. Theoret. Comput. Sci. 2014(6), doi:10.4086/cjtcs.2014.006. arXiv:1302.4207

    2014 arXiv

  30. [38]

    Algo- rithmica 71, pp

    Ashley Montanaro, Richard Jozsa & Graeme Mitchison (2015): On exact quantum query complexity. Algo- rithmica 71, pp. 775–796, doi:10.1007/s00453-013-9826-8. arXiv:1111.0475

    2015 arXiv

  31. [39]

    Nature Commun

    Ognyan Oreshkov, Fabio Costa & ˇCaslav Brukner (2012): Quantum correlations with no causal order. Nature Commun. 3(1), p. 1092, doi:10.1038/ncomms2076. arXiv:1105.4464

    2012 arXiv

  32. [40]

    Ognyan Oreshkov & Christina Giarmatzi (2016): Causal and causally separable processes . New J. Phys. 18(9), p. 093020, doi:10.1088/1367-2630/18/9/093020. arXiv:1506.05449

    2016 arXiv

  33. [41]

    Simon (1997): On the Power of Quantum Computation

    Daniel R. Simon (1997): On the Power of Quantum Computation. SIAM J. Comput. 26(5), pp. 1474–1483, doi:10.1137/S0097539796298637

    1997 doi

  34. [42]

    Taddei, Jaime Cariñe, Daniel Martínez, Tania García, Nayda Guerrero, Alastair A

    Márcio M. Taddei, Jaime Cariñe, Daniel Martínez, Tania García, Nayda Guerrero, Alastair A. Abbott, Mateus Araújo, Cyril Branciard, Esteban S. Gómez, Stephen P. Walborn, Leandro Aolita & Gustavo Lima (2021): Computational advantage from the quantum superposition of multiple tem...

    2021 arXiv

  35. [43]

    Abbott & Cyril Branciard (2019): On the definition and characterisation of multipartite causal (non) separability

    Julian Wechs, Alastair A. Abbott & Cyril Branciard (2019): On the definition and characterisation of multipartite causal (non) separability . New J. Phys. 21(1), p. 013027, doi:10.1088/1367-2630/aaf352. arXiv:1807.10557

    2019 arXiv

  36. [44]

    back in time

    Julian Wechs, Hippolyte Dourdent, Alastair A. Abbott & Cyril Branciard (2021): Quantum Cir- cuits with Classical Versus Quantum Control of Causal Order . PRX Quantum 2, p. 030335, doi:10.1103/PRXQuantum.2.030335. arXiv:2101.08796. A Classical-deterministic supermaps and genera...

    2021 arXiv

  37. [45]

    Then there exist (i′ 1,i′ 2,i′

    ∈ {0,1}6 is another fixed-point of wLugano under the func- tions (µk)k∈{1,2,3}. Then there exist (i′ 1,i′ 2,i′

  38. [46]

    (52) This shows that (i′ 1,i′ 2,i′

    ∈ {0,1}3 such that wk µ1( j′ 1), µ2( j′ 2), µ3( j′ 3) = k + 3 · wk µ1( j′ 1), µ2( j′ 2), µ3( j′ 3) , (50) = k + 3 · i′ k, (51) = j′ k. (52) This shows that (i′ 1,i′ 2,i′

  39. [47]

    classical

    must also be a fixed-point of wLugano under the functions {µk}k∈{1,2,3}, but because the Lugano is logically consistent this fixed-point is unique, and we have for 1 ≤ k ≤ 3, i′ k = ik and therefore j′ k = jk. Finally, to show that wLugano computes f6c, we verify that for any ...

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.