possible separations for higher-degree functions. Although these functions
have not shown any prospect for advantage under the NMQC⊕ model, they guided
us to other computational models with potential advantages. Also, they can
still solve non-local games for which classical circuit analogues fail.
Therefore, their computation using the NMQC⊕model could still be an exciting
element for the study of non-locality and contextuality.

Furthermore, we highlight that proving the conjectured lower bound for the
number of qubits necessary to evaluate an SBF on the NMQC⊕ model would be an
exciting result. It directly affects the understanding of the model, and it
would be an interesting result for understanding non-local correlations. We
state this because each Boolean function relates to a specific Bell inequality
[20]. Thus, results on one front relate to the other, and optimal violations
of Bell inequalities are very difficult to define for arbitrary system sizes
[25]. In addition, such a result would be valuable to test the conjecture
presented by [31, 32, 33], which attempts to axiomatize quantum mechanics from
information theoretical assumptions. For instance, in [91, 92] the authors
define axioms based on communication complexity problems. In particular, their
axiom states that correlations that would allow our physical universe to solve
these problems trivially are forbidden. Then, if this particular hypothesis is
correct, one should retrieve quantum correlations from the maximum allowed by
the non-triviality constraint. Interestingly, in [30], the $C^{2}$ was used as
a non-local black box for which the authors recovered the maximal allowed
efficiency at a constant distance from the corresponding maximal quantum
efficiency. Therefore, introducing lower bounds for other SBFs would provide
more tests for this concept, given that one can analyze any non-local box and
compare the respective maximal quantum correlations to their maximal
efficiency.

We showed that a circuit advantage in the NMQC⊕ model is possible for
evaluating certain Boolean functions with a degree equal to two. However,
these computations were proven inefficient for particular higher degree
functions compared to the best-known classical circuits. This limitation
motivates the extension of the algebraic tools used for the non-adaptive case
to temporally-structured computations. In particular, one could potentially
connect this computational framework to other circuit synthesis techniques
[93], classical algebraic techniques [94], or some existing quantum signal
processing techniques [95, 96]. The possible results from using these new
techniques could be the discovery of compact quantum circuits with potential
advantages. Also, they could describe possible trade-offs between space and
computational time.

For both extreme cases of minimal depth or width, it would be interesting to
understand if circuits exhibit some quantum advantage. For instance, for the
depth necessary to evaluate the Boolean $\mathsf{OR}$ function defined on any
possible size of the input string, one could expect an advantage [97, 98, 99].
In particular, in [100], the use of a single adaptive step demonstrated an
exponential reduction of the number of qubits for the same function. The same
separation was then generalized equally with a single adaptive step for
arbitrary symmetric Boolean functions in [21] and with a constant number of
adaptive steps in [101] resorting to the previously mentioned quantum signal
processing techniques. Identically, suppose one does try to minimize the
computational space. In that case, the quantum circuits could have some width
advantage. Interestingly, for a small computational space, a separation was
already identified in [49, 48, 87], and experimentally explored on IBM’s
quantum devices [48]. Nevertheless, we question whether the width separations
for quantum and classical computations hold for computations with unbounded
width and arbitrary input size. Our results seem to indicate that this could
indeed be the case.

Another type of analysis would be focused on an intermediate class of quantum
circuits. For that, we consider the circuits class composed of quantum layers
that can only pass classical information between them. Remember that for MBQC
computations, the various quantum layers are entangled. Therefore, there is a
quantum and a classical channel between each layer 131313Some initial ideas on
how to describe a quantum wire that transmits information between layers have
been proposed in [102].. In addition, the computational capacity of this
intermediate class is not entirely understood [21, 103]. However, if they
present any advantage, they are easier to implement in Noisy, intermediate-
scale quantum devices (NISQ), being therefore attractive candidates for
experimental realizations [104]. That reduction in the hardware requirements
relates to the fact that these circuits demand less connectivity between the
qubits and coherence of the gates. In the end, describing such intermediate
complexity classes could be a very appealing task to understand further the
importance of a temporal structure in general quantum computations and other
particular circuits with advantages [39, 43].

Finally, we hope this work will inspire more experiments like the ones
described in [105, 101, 106], to verify the computational capabilities of
quantum correlations with realizations equivalent to the NMQC⊕ model.
Moreover, as other works have shown, these realizations could work as a device
benchmarking tool [107, 108, 109, 110, 111]. Independently, the ideas explored
in this paper are also connected to some secure multi-party computation
protocols [112], which consider clients with limited computational power.
Therefore, we believe that the techniques developed here could allow the
design of new and better protocols. These could then potentially motivate
exciting experiments, such as the ones reported in [113, 114].

Acknowledgments We acknowledge helpful feedback from Dan Browne and Pedro
Patricio on an early version of these results. This work is financed by
National Funds through the FCT - Fundação para a Ciência e a Tecnologia, I.P.
(Portuguese Foundation for Science and Technology) within the project IBEX,
with reference PTDC/CCI-COM/4280/2021, and via CEECINST/00062/2018 (EFG). This
work was supported by the H2020-FETOPEN Grant PHOQUSING (GA no.:899544).

## References

  * [1] Scott Aaronson, DeVon Ingram, and William Kretschmer.  “The acrobatics of bqp” (2021).  url: doi.org/10.48550/arXiv.2111.10409.
  * [2] Richard Jozsa and Noah Linden.  “On the role of entanglement in quantum-computational speed-up”.  Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences 459, 2011–2032 (2003).  url: doi.org/10.1098/rspa.2002.1097.
  * [3] Mark Howard, Joel Wallman, Victor Veitch, and Joseph Emerson.  “Contextuality supplies the ‘magic’ for quantum computation”.  Nature 510, 351–355 (2014).  url: doi.org/10.1038/nature13460.
  * [4] Juan Bermejo-Vega, Nicolas Delfosse, Dan E Browne, Cihan Okay, and Robert Raussendorf.  “Contextuality as a resource for models of quantum computation with qubits”.  Physical review letters 119, 120505 (2017).  url: link.aps.org/doi/10.1103/PhysRevLett.119.120505.
  * [5] Ernesto F Galvão.  “Discrete Wigner functions and quantum computational speedup”.  Phys. Rev. A 71, 042302 (2005).  url: link.aps.org/doi/10.1103/PhysRevA.71.042302.
  * [6] A Mari and J Eisert.  “Positive Wigner Functions Render Classical Simulation of Quantum Computation Efficient”.  Phys. Rev. Lett. 109, 230503 (2012).  url: link.aps.org/doi/10.1103/PhysRevLett.109.230503.
  * [7] Lov K Grover.  “The advantages of superposition”.  Science 280, 228 (1998).  url: www.science.org/doi/10.1126/science.280.5361.228.
  * [8] Robert Raussendorf and Hans J Briegel.  “A one-way quantum computer”.  Phys. Rev. Lett. 86, 5188–5191 (2001).  url: link.aps.org/doi/10.1103/PhysRevLett.86.5188.
  * [9] Maarten Van den Nest, Akimasa Miyake, Wolfgang Dür, and Hans J Briegel.  “Universal resources for measurement-based quantum computation”.  Physical review letters 97, 150504 (2006).  url: link.aps.org/doi/10.1103/PhysRevLett.97.150504.
  * [10] Janet Anders and Dan E. Browne.  “Computational power of correlations”.  Phys. Rev. Lett. 102, 050502 (2009).
  * [11] Vincent Danos and Elham Kashefi.  “Determinism in the one-way model”.  Phys. Rev. A 74, 052310 (2006).
  * [12] Daniel E Browne, Elham Kashefi, Mehdi Mhalla, and Simon Perdrix.  “Generalized flow and determinism in measurement-based quantum computation”.  New Journal of Physics 9, 250 (2007).
  * [13] Michael J Bremner, Ashley Montanaro, and Dan J Shepherd.  “Average-Case Complexity Versus Approximate Simulation of Commuting Quantum Computations”.  Phys. Rev. Lett. 117, 080501 (2016).
  * [14] Matty J Hoban, Joel J Wallman, Hussain Anwar, Naïri Usher, Robert Raussendorf, and Dan E Browne.  “Measurement-based classical computation”.  Physical review letters 112, 140505 (2014).  url: link.aps.org/doi/10.1103/PhysRevLett.112.140505.
  * [15] Michael J Bremner, Ashley Montanaro, and Dan J Shepherd.  “Achieving quantum supremacy with sparse and noisy commuting quantum computations”.  Quantum 1, 8 (2017).  url: doi.org/10.22331/q-2017-04-25-8.
  * [16] Leonardo Novo, Juani Bermejo-Vega, and Raúl García-Patrón.  “Quantum advantage from energy measurements of many-body quantum systems”.  Quantum 5, 465 (2021).
  * [17] Masahito Hayashi and Yuki Takeuchi.  “Verifying commuting quantum computations via fidelity estimation of weighted graph states”.  New Journal of Physics 21, 93060 (2019).
  * [18] Juan Bermejo-Vega, Dominik Hangleiter, Martin Schwarz, Robert Raussendorf, and Jens Eisert.  “Architectures for Quantum Simulation Showing a Quantum Speedup”.  Phys. Rev. X 8, 021010 (2018).
  * [19] Jacob Miller, Stephen Sanders, and Akimasa Miyake.  “Quantum supremacy in constant-time measurement-based computation: A unified architecture for sampling and verification”.  Phys. Rev. A 96, 062320 (2017).
  * [20] Matty J Hoban, Earl T Campbell, Klearchos Loukopoulos, and Dan E Browne.  “Non-adaptive measurement-based quantum computation and multi-party Bell inequalities”.  New Journal of Physics 13, 23014 (2011).
  * [21] Ryuhei Mori.  “Periodic Fourier representation of Boolean functions”.  Quantum Info. Comput. 19, 392–412 (2019).  url: dl.acm.org/doi/abs/10.5555/3370251.3370253.
  * [22] Markus Frembs, Sam Roberts, Earl T Campbell, and Stephen D Bartlett.  “Hierarchies of resources for measurement-based quantum computation” (2022).  url: arxiv.org/abs/2203.09965.
  * [23] Jelena Mackeprang, Daniel Bhatti, Matty J Hoban, and Stefanie Barz.  “The power of qutrits for non-adaptive measurement-based quantum computing” (2022).  url: arxiv.org/abs/2203.12411.
  * [24] Daniel Collins, Nicolas Gisin, Sandu Popescu, David Roberts, and Valerio Scarani.  “Bell-Type Inequalities to Detect True $\mathit{n}$-Body Nonseparability”.  Phys. Rev. Lett. 88, 170405 (2002).
  * [25] Nicolas Brunner, Daniel Cavalcanti, Stefano Pironio, Valerio Scarani, and Stephanie Wehner.  “Bell nonlocality”.  Rev. Mod. Phys. 86, 419–478 (2014).
  * [26] Dmitrijs Kravčenko.  “Quantum Games, Quantum States, Their Properties and Applications”.  PhD thesis.  Latvijas Universitāte.  (2013).
  * [27] William Slofstra.  “Lower bounds on the entanglement needed to play XOR non-local games”.  Journal of Mathematical Physics 52, 102202 (2011).
  * [28] Andris Ambainis, Jānis Iraids, Dmitry Kravchenko, and Madars Virza.  “Advantage of quantum strategies in random symmetric xor games”.  In Antonín Kučera, Thomas A. Henzinger, Jaroslav Nešetřil, Tomáš Vojnar, and David Antoš, editors, Mathematical and Engineering Methods in Computer Science.  Volume 7721 of Lecture Notes in Computer Science, pages 57–68.  Berlin, Heidelberg (2013). Springer Berlin Heidelberg.  url: doi.org/10.1007/978-3-642-36046-6$\\_$7.
  * [29] Andris Ambainis and Jānis Iraids.  “Provable advantage for quantum strategies in random symmetric xor games” (2013).  url: 10.4230/LIPIcs.TQC.2013.146.
  * [30] Samuel Marcovitch and Benni Reznik.  “Implications of communication complexity in multipartite systems”.  Phys. Rev. A 77, 032120 (2008).
  * [31] Marcin Pawłowski, Tomasz Paterek, Dagomir Kaszlikowski, Valerio Scarani, Andreas Winter, and Marek Żukowski.  “Information causality as a physical principle”.  Nature 461, 1101–1104 (2009).
  * [32] Sandu Popescu and Daniel Rohrlich.  “Quantum nonlocality as an axiom”.  Foundations of Physics 24, 379–385 (1994).
  * [33] Jonathan Barrett, Noah Linden, Serge Massar, Stefano Pironio, Sandu Popescu, and David Roberts.  “Nonlocal correlations as an information-theoretic resource”.  Phys. Rev. A 71, 022101 (2005).
  * [34] Alexander A Razborov.  “Quantum communication complexity of symmetric predicates”.  Izvestiya: Mathematics 67, 145 (2003).  url: iopscience.iop.org/article/10.1070/IM2003v067n01ABEH000422.
  * [35] Zhiqiang Zhang and Yaoyun Shi.  “Communication complexities of symmetric XOR functions”.  Quantum Information and Computation 9, 255–263 (2009).  url: dl.acm.org/doi/abs/10.5555/2011781.2011786.
  * [36] Pierre Botteron.  “NonLocal Boxes and Communication Complexity”.  Master’s thesis.  Université Paul Sabatier Toulouse III.  (2022).
  * [37] Kwangil Bae and Wonmin Son.  “Generalized nonlocality criteria under the correlation symmetry”.  Physical Review A 98, 022116 (2018).  url: doi.org/10.1103/PhysRevA.98.022116.
  * [38] Markus Frembs, Sam Roberts, and Stephen D Bartlett.  “Contextuality as a resource for measurement-based quantum computation beyond qubits”.  New Journal of Physics 20, 103011 (2018).
  * [39] Sergey Bravyi, David Gosset, and Robert König.  “Quantum advantage with shallow circuits”.  Science 362, 308–311 (2018).
  * [40] Daniel Grier and Luke Schaeffer.  “Interactive Shallow Clifford Circuits: Quantum Advantage against NC¹ and Beyond”.  In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing.  Pages 875–888.  STOC 2020New York, NY, USA (2020). Association for Computing Machinery.
  * [41] Libor Caha, Xavier Coiteux-Roy, and Robert Koenig.  “Single-qubit gate teleportation provides a quantum advantage” (2022).  arXiv:2209.14158.
  * [42] François Le Gall.  “Average-Case Quantum Advantage with Shallow Circuits”.  In Amir Shpilka, editor, 34th Computational Complexity Conference (CCC 2019).  Volume 137 of Leibniz International Proceedings in Informatics (LIPIcs), pages 21:1—-21:20.  Dagstuhl, Germany (2019). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  * [43] Matthew Coudron, Jalex Stark, and Thomas Vidick.  “Trading locality for time: certifiable randomness from low-depth circuits”.  Communications in mathematical physics 382, 49–86 (2021).  url: doi.org/10.1007/s00220-021-03963-w.
  * [44] Sergey Bravyi, David Gosset, Robert König, and Marco Tomamichel.  “Quantum advantage with noisy shallow circuits”.  Nature Physics 16, 1040–1045 (2020).
  * [45] Atsuya Hasegawa and François Le Gall.  “Quantum advantage with shallow circuits under arbitrary corruption” (2021).  url: arxiv.org/abs/2105.00603.
  * [46] Adam Bene Watts, Robin Kothari, Luke Schaeffer, and Avishay Tal.  “Exponential Separation between Shallow Quantum Circuits and Unbounded Fan-in Shallow Classical Circuits”.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing.  Pages 515–526.  STOC 2019New York, NY, USA (2019). Association for Computing Machinery.
  * [47] Natalie Parham.  “On the Power and Limitations of Shallow Quantum Circuits”.  Master’s thesis.  University of Waterloo.  (2022).
  * [48] Dmitri Maslov, Jin-Sung Kim, Sergey Bravyi, Theodore J Yoder, and Sarah Sheldon.  “Quantum advantage for computations with limited space”.  Nature Physics 17, 894–897 (2021).
  * [49] Farid Ablayev, Aida Gainutdinova, Marek Karpinski, Cristopher Moore, and Christopher Pollett.  “On the computational power of probabilistic and quantum branching program”.  Information and Computation 203, 145–162 (2005).  url: doi.org/10.1016/j.ic.2005.04.003.
  * [50] Tzu-Chieh Wei.  “Measurement-based quantum computation” (2021).  url: arxiv.org/abs/2109.10111.
  * [51] D Shepherd and M. J. Bremner.  “Temporally unstructured quantum computation”.  Proceedings of the Royal Society of London Series A 465, 1413–1439 (2009).  arXiv:0809.0847.
  * [52] Daniel M Greenberger, Michael A Horne, and Anton Zeilinger.  “Going Beyond Bell’s Theorem”.  In Menas Kafatos, editor, Bell’s Theorem, Quantum Theory and Conceptions of the Universe.  Pages 69–72.  Dordrecht (1989). Springer Netherlands.
  * [53] Diogo Cruz, Romain Fournier, Fabien Gremion, Alix Jeannerot, Kenichi Komagata, Tara Tosic, Jarla Thiesbrummel, Chun Lam Chan, Nicolas Macris, Marc-André Dupertuis, and Clément Javerzac-Galy.  “Efficient Quantum Algorithms for GHZ and W States, and Implementation on the IBM Quantum Computer”.  Advanced Quantum Technologies 2, 1900015 (2019).
  * [54] R Werner and M Wolf.  “All-multipartite Bell-correlation inequalities for two dichotomic observables per site”.  Physical Review A 64, 032112 (2001).  url: link.aps.org/doi/10.1103/PhysRevA.64.032112.
  * [55] Ryan O’Donnell.  “Analysis of boolean functions”.  Cambridge University Press. (2014).  url: http://www.cs.cmu.edu/ ./odonnell/papers/Analysis-of-Boolean-Functions-by-Ryan-ODonnell.pdf.
  * [56] Anastasiya Chistopolskaya and Vladimir V Podolskii.  “Parity Decision Tree Complexity is Greater Than Granularity” (2018).  url: arxiv.org/abs/1810.08668.
  * [57] A Canteaut and M Videau.  “Symmetric Boolean functions”.  IEEE Transactions on Information Theory 51, 2791–2811 (2005).
  * [58] Larry J Stockmeyer.  “On the combinational complexity of certain symmetric Boolean functions”.  Mathematical systems theory 10, 323–336 (1976).
  * [59] R F Arnold and M A Harrison.  “Algebraic Properties of Symmetric and Partially Symmetric Boolean Functions”.  IEEE Transactions on Electronic Computers EC-12, 244–251 (1963).
  * [60] An Braeken and Bart Preneel.  “On the algebraic immunity of symmetric boolean functions”.  In Subhamoy Maitra, C. E. Veni Madhavan, and Ramarathnam Venkatesan, editors, Progress in Cryptology - INDOCRYPT 2005.  Volume 3797 of Lecture Notes in Computer Science, pages 35–48.  Berlin, Heidelberg (2005). Springer Berlin Heidelberg.  url: doi.org/10.1007/11596219$\\_$4.
  * [61] Harry Buhrman and Ronald de Wolf.  “Complexity measures and decision tree complexity: a survey”.  Theoretical Computer Science 288, 21–43 (2002).
  * [62] Matthew Amy, Dmitri Maslov, Michele Mosca, and Martin Roetteler.  “A Meet-in-the-Middle Algorithm for Fast Synthesis of Depth-Optimal Quantum Circuits”.  IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 32, 818–830 (2013).
  * [63] V V Shende, S S Bullock, and I L Markov.  “Synthesis of quantum-logic circuits”.  IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 25, 1000–1010 (2006).
  * [64] Juha J Vartiainen, Mikko Möttönen, and Martti M Salomaa.  “Efficient Decomposition of Quantum Gates”.  Phys. Rev. Lett. 92, 177902 (2004).
  * [65] Bei Zeng, Xie Chen, and Isaac L Chuang.  “Semi-Clifford operations, structure of $\mathcal{C}_{k}$ hierarchy, and gate complexity for fault-tolerant quantum computation”.  Phys. Rev. A 77, 042313 (2008).
  * [66] Gary J Mooney, Charles D Hill, and Lloyd C L Hollenberg.  “Cost-optimal single-qubit gate synthesis in the Clifford hierarchy”.  Quantum 5, 396 (2021).
  * [67] Nadish de Silva.  “Efficient quantum gate teleportation in higher dimensions”.  Proceedings of the Royal Society A 477, 20200865 (2021).  url: doi.org/10.1098/rspa.2020.0865.
  * [68] Daniel Gottesman and Isaac L Chuang.  “Demonstrating the viability of universal quantum computation using teleportation and single-qubit operations”.  Nature 402, 390–393 (1999).  url: doi.org/10.1038/46503.
  * [69] Daniel Gottesman.  “The heisenberg representation of quantum computers” (1998).  url: arxiv.org/abs/quant-ph/9807006.
  * [70] Vadym Kliuchnikov, Dmitri Maslov, and Michele Mosca.  “Fast and Efficient Exact Synthesis of Single-Qubit Unitaries Generated by Clifford and T Gates”.  Quantum Info. Comput. 13, 607–630 (2013).  url: dl.acm.org/doi/abs/10.5555/2535649.2535653.
  * [71] Nicolas Brunner, James Sharam, and Tamás Vértesi.  “Testing the structure of multipartite entanglement with Bell inequalities.”.  Physical review letters 108 11, 110501 (2012).  url: doi.org/10.1103/PhysRevLett.108.110501.
  * [72] Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Ben Toner, and Thomas Vidick.  “Entangled Games Are Hard to Approximate”.  SIAM Journal on Computing 40, 848–877 (2011).
  * [73] Yihui Quek, Mark M Wilde, and Eneet Kaur.  “Multivariate trace estimation in constant quantum depth” (2022).  arXiv:2206.15405.
  * [74] Peter Selinger.  “Efficient Clifford+T Approximation of Single-Qubit Operators”.  Quantum Info. Comput. 15, 159–180 (2015).  url: dl.acm.org/doi/abs/10.5555/2685188.2685198.
  * [75] Vadym Kliuchnikov, Dmitri Maslov, and Michele Mosca.  “Practical Approximation of Single-Qubit Unitaries by Single-Qubit Quantum Clifford and T Circuits”.  IEEE Transactions on Computers 65, 161–172 (2016).
  * [76] Neil J Ross.  “Optimal Ancilla-Free CLIFFORD+V Approximation of Z-Rotations”.  Quantum Info. Comput. 15, 932–950 (2015).  url: dl.acm.org/doi/abs/10.5555/2871350.2871354.
  * [77] Ethan Bernstein and Umesh Vazirani.  “Quantum Complexity Theory”.  In Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing.  Pages 11–20.  STOC ’93New York, NY, USA (1993). Association for Computing Machinery.
  * [78] Alex Bocharov, Martin Roetteler, and Krysta M Svore.  “Efficient synthesis of probabilistic quantum circuits with fallback”.  Phys. Rev. A 91, 052317 (2015).
  * [79] Alex Bocharov, Martin Roetteler, and Krysta M Svore.  “Efficient Synthesis of Universal Repeat-Until-Success Quantum Circuits”.  Phys. Rev. Lett. 114, 080502 (2015).
  * [80] Ingo Wegener.  “The Complexity of Boolean Functions”.  John Wiley $\&$ Sons, Inc. USA (1987).  url: dl.acm.org/doi/abs/10.5555/35517.
  * [81] Heribert Vollmer.  “Introduction to Circuit Complexity: A Uniform Approach”.  Springer Publishing Company, Incorporated. (2010).  1st edition.  url: link.springer.com/book/10.1007/978-3-662-03927-4.
  * [82] R Smolensky.  “Algebraic Methods in the Theory of Lower Bounds for Boolean Circuit Complexity”.  In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing.  Pages 77–82.  STOC ’87New York, NY, USA (1987). Association for Computing Machinery.
  * [83] Jaikumar Radhakrishnan.  “Better bounds for threshold formulas”.  In [1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science.  Pages 314–323.  IEEE Computer Society (1991).
  * [84] Michael J Fischer, Albert R Meyer, and Michael S Paterson.  “$\Omega(N\log n)$ Lower Bounds on Length of Boolean Formulas”.  SIAM J. Comput. 11, 416–427 (1982).
  * [85] Sanjeev Arora and Boaz Barak.  “Computational Complexity: A Modern Approach”.  Cambridge University Press. USA (2009).  1st edition.  url: dl.acm.org/doi/abs/10.5555/1540612.
  * [86] Scott Aaronson.  “How Much Structure Is Needed for Huge Quantum Speedups?” (2022).  arXiv:2209.06930.
  * [87] David A Barrington.  “Bounded-width polynomial-size branching programs recognize exactly those languages in NC1”.  Journal of Computer and System Sciences 38, 150–164 (1989).
  * [88] Scott Aaronson and Alex Arkhipov.  “The Computational Complexity of Linear Optics”.  In Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing.  Pages 333–342.  STOC ’11New York, NY, USA (2011). Association for Computing Machinery.
  * [89] Peter W Shor.  “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”.  SIAM Review 41, 303–332 (1999).
  * [90] Daniel R Simon.  “On the Power of Quantum Computation”.  SIAM Journal on Computing 26, 1474–1483 (1997).
  * [91] Gilles Brassard, Harry Buhrman, Noah Linden, André Allan Méthot, Alain Tapp, and Unger Falk.  “Limit on Nonlocality in Any World in Which Communication Complexity Is Not Trivial”.  Phys. Rev. Lett. 96, 250401 (2006).
  * [92] Wim van Dam.  “Implausible consequences of superstrong nonlocality”.  Natural Computing 12, 9–12 (2013).
  * [93] Matthew Amy and Michele Mosca.  “T-Count Optimization and Reed–Muller Codes”.  IEEE Transactions on Information Theory 65, 4771–4784 (2019).
  * [94] Peter Bürgisser, Michael Clausen, and Mohammad A Shokrollahi.  “Algebraic complexity theory”.  Volume 315.  Springer Science & Business Media. (2013).  url: dl.acm.org/doi/abs/10.5555/1965416.
  * [95] Guang Hao Low and Isaac L. Chuang.  “Optimal hamiltonian simulation by quantum signal processing”.  Phys. Rev. Lett. 118, 010501 (2017).
  * [96] Jeongwan Haah.  “Product Decomposition of Periodic Functions in Quantum Signal Processing”.  Quantum 3, 190 (2019).
  * [97] Scott Aaronson, Shalev Ben-David, Robin Kothari, Shravas Rao, and Avishay Tal.  “Degree vs. Approximate Degree and Quantum Implications of Huang’s Sensitivity Theorem”.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing.  Pages 1330–1342.  STOC 2021New York, NY, USA (2021). Association for Computing Machinery.
  * [98] Hao Huang.  “Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture”.  Annals of Mathematics 190, 949–955 (2019).
  * [99] Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, and Juris Smotrovs.  “Separations in Query Complexity Based on Pointer Functions”.  J. ACM64 (2017).
  * [100] Peter Hoyer and Robert Spalek.  “Quantum Circuits with Unbounded Fan-out” (2002).  arXiv:quant-ph/0208043.
  * [101] Austin K Daniel, Yingyue Zhu, C Huerta Alderete, Vikas Buchemmavari, Alaina M Green, Nhung H Nguyen, Tyler G Thurtell, Andrew Zhao, Norbert M Linke, and Akimasa Miyake.  “Quantum computational advantage attested by nonlocal games with the cyclic cluster state”.  Phys. Rev. Research 4, 033068 (2022).
  * [102] Paul Herringer and Robert Raussendorf.  “Classification of measurement-based quantum wire in stabilizer PEPS” (2022).  arXiv:2207.00616.
  * [103] Abhishek Anand.  “On the power of interleaved low-depth quantum and classical circuits”.  Master’s thesis.  University of Waterloo.  (2022).
  * [104] John Preskill.  “Quantum Computing in the NISQ era and beyond”.  Quantum 2, 79 (2018).
  * [105] Bülent Demirel, Weikai Weng, Christopher Thalacker, Matty Hoban, and Stefanie Barz.  “Correlations for computation and computation for correlations”.  npj Quantum Information 7, 1–8 (2021).  url: doi.org/10.1038/s41534-020-00354-2.
  * [106] Manoranjan Swain, Amit Rai, Bikash K Behera, and Prasanta K Panigrahi.  “Experimental demonstration of the violations of Mermin’s and Svetlichny’s inequalities for W and GHZ states”.  Quantum Information Processing 18, 218 (2019).
  * [107] Bo Yang, Rudy Raymond, Hiroshi Imai, Hyungseok Chang, and Hidefumi Hiraishi.  “Testing scalable bell inequalities for quantum graph states on ibm quantum devices”.  IEEE Journal on Emerging and Selected Topics in Circuits and Systems 12, 638–647 (2022).
  * [108] F. Baccari, R. Augusiak, I. Šupić, J. Tura, and A. Acín.  “Scalable bell inequalities for qubit graph states and robust self-testing”.  Phys. Rev. Lett. 124, 020402 (2020).
  * [109] Ken X Wei, Isaac Lauer, Srikanth Srinivasan, Neereja Sundaresan, Douglas T McClure, David Toyli, David C McKay, Jay M Gambetta, and Sarah Sheldon.  “Verifying multipartite entangled Greenberger-Horne-Zeilinger states via multiple quantum coherences”.  Phys. Rev. A 101, 032343 (2020).
  * [110] Wei-Jia Huang, Wei-Chen Chien, Chien-Hung Cho, Che-Chun Huang, Tsung-Wei Huang, and Ching-Ray Chang.  “Mermin’s inequalities of multiple qubits with orthogonal measurements on IBM Q 53-qubit system”.  Quantum Engineering 2, e45 (2020).
  * [111] Meron Sheffer, Daniel Azses, and Emanuele G Dalla Torre.  “Playing Quantum Nonlocal Games with Six Noisy Qubits on the Cloud”.  Advanced Quantum Technologies 5, 2100081 (2022).
  * [112] Vedran Dunjko, Theodoros Kapourniotis, and Elham Kashefi.  “Quantum-Enhanced Secure Delegated Classical Computing”.  Quantum Info. Comput. 16, 61–86 (2016).  url: dl.acm.org/doi/abs/10.5555/3179320.3179325.
  * [113] Stefanie Barz, Vedran Dunjko, Florian Schlederer, Merritt Moore, Elham Kashefi, and Ian A. Walmsley.  “Enhanced delegated computing using coherence”.  Phys. Rev. A 93, 032339 (2016).
  * [114] Marco Clementi, Anna Pappa, Andreas Eckstein, Ian A Walmsley, Elham Kashefi, and Stefanie Barz.  “Classical multiparty computation using quantum resources”.  Physical Review A 96, 062317 (2017).
  * [115] Nasir Ahmed and Kamisetty Ramamohan Rao.  “Walsh-hadamard transform”.  In Orthogonal transforms for digital signal processing.  Pages 99–152.  Springer (1975).
  * [116] Michael A Nielsen and Isaac L Chuang.  “Quantum Computation and Quantum Information: 10th Anniversary Edition”.  Cambridge University Press. (2010).
  * [117] Philip Feinsilver and Jerzy Kocik.  “Krawtchouk polynomials and krawtchouk matrices”.  Pages 115–141.  Recent Advances in Applied Probability. Springer US. Boston, MA (2005).
  * [118] Philip Feinsilver and Rene Schott.  “Krawtchouk transforms and convolutions”.  Bulletin of Mathematical SciencesPages 1–19 (2018).  url: doi.org/10.1007/s13373-018-0132-2.
  * [119] Magdalena Stobińska, A Buraczewski, M Moore, W R Clements, Jelmer Jan Renema, S W Nam, T Gerrits, A Lita, W S Kolthammer, Andreas Eckstein, and Others.  “Quantum interference enables constant-time quantum information processing”.  Science advances 5, eaau9674 (2019).  url: www.science.org/doi/full/10.1126/sciadv.aau9674.
  * [120] Raymond Greenwell and Stanley Kertzner.  “Solving Linear Diophantine Matrix Equations Using the Smith Normal Form (More or Less)”.  International Journal of Pure and Applied Mathematics55 (2009).  url: ijpam.eu/contents/2009-55-1/7/index.html.
  * [121] Ravindran Kannan and Achim Bachem.  “Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix”.  SIAM Journal on Computing 8, 499–507 (1979).
  * [122] Josh Alman and Virginia Vassilevska Williams.  “A refined laser method and faster matrix multiplication”.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA).  Pages 522–539.  SIAM (2021).  url: epubs.siam.org/doi/abs/10.1137/1.9781611976465.32.

##  Appendix A Mathematical transformations

###  A.1 Walsh-Hadamard transform

The Walsh-Hadamard transform [115, 116] $\mathcal{F}$ is a Fourier transform
that has their characters $X_{S}(x)$ defined as

$X_{S}(x)=\left\\{\begin{array}[]{ll}\prod_{i\in
S}x_{i},&S\subseteq([n]\setminus\emptyset)\\\
1,&S=\emptyset\end{array}\right.\ ,$ (97)

with $x\in\\{1,-1\\}^{n}$ and $S\subseteq[n]$. These characters are the real
parity functions that are used to define the multi-linear polynomials
(Definition 2). Moreover, the matrix that defines the transformation is
composed of all possible characters $X_{S}(x)$ that can be computed based on
the size of the input string $S\subseteq[n]$ evaluated over all possible input
values $x\in\\{1,-1\\}^{n}$,

$\mathcal{F}=\begin{bmatrix}X_{S_{1}}(x_{1})&X_{S_{2}}(x_{1})&X_{S_{3}}(x_{1})&...&X_{S_{2^{n}}}(x_{1})\\\
X_{S_{1}}(x_{2})&X_{S_{2}}(x_{2})&X_{S_{3}}(x_{2})&...&X_{S_{2^{n}}}(x_{2})\\\
X_{S_{1}}(x_{3})&X_{S_{2}}(x_{3})&X_{S_{3}}(x_{3})&...&X_{S_{2^{n}}}(x_{3})\\\
\vdots&\vdots&\vdots&\ldots&\vdots\\\
X_{S_{1}}(x_{2^{n}})&X_{S_{2}}(x_{2^{n}})&X_{S_{2}}(x_{2^{n}})&...&X_{S_{2^{n}}}(x_{2^{n}})\end{bmatrix}\
.$ (98)

Furthermore, the transposed matrix of the Walsh-Hadamard transform applied to
the column vector containing the truth table of the Boolean function generates
the Fourier coefficients,

$\frac{1}{2^{n}}\begin{bmatrix}X_{S_{1}}(x_{1})&X_{S_{1}}(x_{2})&X_{S_{1}}(x_{2})&...&X_{S_{1}}(x_{2^{n}})\\\
X_{S_{2}}(x_{1})&X_{S_{2}}(x_{2})&X_{S_{2}}(x_{2})&...&X_{S_{2}}(x_{2^{n}})\\\
X_{S_{3}}(x_{1})&X_{S_{3}}(x_{2})&X_{S_{3}}(x_{2})&...&X_{S_{3}}(x_{2^{n}})\\\
\vdots&\vdots&\vdots&\ldots&\vdots\\\
X_{S_{2^{n}}}(x_{1})&X_{2^{n}}(x_{2})&X_{2^{n}}(x_{2})&...&X_{2^{n}}(x_{2^{n}})\end{bmatrix}*\begin{bmatrix}f(x_{1})\\\
f(x_{2})\\\ f(x_{3})\\\ \vdots\\\ f(x_{2^{n}})\end{bmatrix}\\\
=\begin{bmatrix}\widehat{f}(S_{1})\\\ \widehat{f}(S_{2})\\\
\widehat{f}(S_{3})\\\ \vdots\\\ \widehat{f}(S_{2^{n}})\\\ \end{bmatrix}\ .$
(99)

Given that, every element of the resulting column vector is derived from the
equation

$\widehat{f}(S)=\sum_{x_{i}\in\\{0,1\\}^{n}}f(x_{i})X_{S}(g^{-1}(x_{i}))\ ,$
(100)

which computes the Fourier coefficient of the Boolean function [55].

###  A.2 Krawtchouk transform

The Krawtchouk transform [117, 118, 119], $\mathcal{K}$ is defined by a matrix
with entries specified by the following expressions,

$K_{i,j}=\begin{cases}\sum_{k=0}^{i}(-1)^{k}\binom{j}{k}\binom{n-j}{i-k},&i<j\
and\ i+j<=n\\\ \sum_{k=0}^{j}(-1)^{k}\binom{j}{k}\binom{n-j}{i-k},&i>=j\ and\
i+j<n\\\ \sum_{k=j+i-n}^{j}(-1)^{k}\binom{j}{k}\binom{n-j}{i-k},&i>=j\ and\
i+j>=n\\\ \sum_{k=0}^{n-j}(-1)^{i-k}\binom{j}{i-k}\binom{n-j}{k},&i<j\ and\
i+j>n\\\ \end{cases}\ .$ (101)

The matrix has, therefore, the following form,

$\mathcal{K}^{[n]}=\begin{bmatrix}\binom{n}{0}&\binom{n}{1}&...&\binom{n}{i}&...&\binom{n}{n}\\\
\binom{n-1}{0}&-\binom{n-1}{0}+\binom{n-1}{1}&...&-\binom{n-1}{1}+\binom{n-1}{2}&...&-\binom{n-1}{n-1}\\\
\binom{n-2}{0}&-2\binom{n-2}{0}+\binom{n-2}{1}&...&\binom{n-2}{0}-2\binom{n-2}{1}+\binom{n-2}{2}&...&\binom{n-2}{n-2}\\\
\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\\
\binom{n-j}{0}&\ldots&\ldots&rf_{i,j}=\sum_{k=0}^{j}(-1)^{j-k}\binom{j}{k}\binom{n-j}{i-k}&\ldots&(-1)^{j}\binom{n-j}{n-j}\\\
\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\\
(-1)^{0}\binom{n}{n}&(-1)^{1}\binom{n}{n-1}&\ldots&(-1)^{i}\binom{n}{n-i}&\ldots&(-1)^{i=j}\binom{n}{0}\\\
\end{bmatrix}$ (102)

with dimension $n+1\times n+1$.

##  Appendix B Proof of Lemma 1

This section proves that any complete symmetric function $C^{k}$ can be
decomposed into a conjunction formed uniquely with CSF with a degree equal to
a power of two $C^{2^{r}}$. We obtain the following lemma for single
conjunction.

######  Lemma 12.

The composition of two complete symmetric functions with degrees $p$ and $q$
equals the complete symmetric function with degree $p+q$,

$C^{p}\wedge C^{q}=C^{p+q}$ (103)

if $q$ is a power of two and $p$ is a number composed of powers two larger
than $q$, i.e. $p=\sum_{i\in N}2^{n_{i}},\ q=2^{m},\forall i\in N\ (n_{i}>m)$

###### Proof.

We proceed by strong induction.

Base case:

$C^{p}\wedge C^{1}=C^{p+1},with\ p=\sum_{i\in N}2^{n_{i}},\forall_{i\in N}\
(n_{i}>0)$ (104)

To prove this equality, we resort to its ANFs,

$\underbrace{\Big{(}\underset{1\leq i_{1}<i_{2}<...\leq
k}{\bigoplus}x_{i_{1}}\wedge x_{i_{2}}\wedge...\wedge
x_{i_{p}}\Big{)}}_{Exp_{1}}\ \wedge\
\underbrace{\overset{k}{\underset{i=0}{\bigoplus}}\
x_{i}}_{Exp_{2}}=\underset{1\leq i_{1}<i_{2}<...\leq
k}{\bigoplus}x_{i_{1}}\wedge x_{i_{2}}\wedge...\wedge x_{i_{p+1}}$ (105)

and apply the AND operator to verify that LHS equals the RHS. However, the
expression will contain terms that are not only simple linear sums of AND
operators composed of single bits. The following rule will reduce the terms
with linear sums inside the AND operators possible

$(a\oplus b)\wedge c=(a\wedge c)\oplus(b\wedge c)$ (R1)

By applying repeatedly Rule R1 to the LHS of Equation (105) we obtain an
expression with a term for each element of $Exp_{2}$ composed with $Exp_{1}$

$\displaystyle\begin{split}&C^{p}\wedge C^{1}=\\\
&\Big{(}\Big{(}\underbrace{\underset{1\leq i_{1}<i_{2}<...\leq
k}{\bigoplus}x_{i_{1}}\wedge x_{i_{2}}\wedge...\wedge
x_{i_{p}}\Big{)}}_{Exp1}\wedge
x_{1}\Big{)}\oplus\Big{(}\Big{(}\underbrace{\underset{1\leq
i_{1}<i_{2}<...\leq k}{\bigoplus}x_{i_{1}}\wedge x_{i_{2}}\wedge...\wedge
x_{i_{p}}\Big{)}}_{Exp1}\wedge x_{2}\Big{)}\\\ &\oplus\ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \cdot\cdot\cdot\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \oplus\Big{(}\Big{(}\underbrace{\underset{1\leq i_{1}<i_{2}<...\leq
k}{\bigoplus}x_{i_{1}}\wedge x_{i_{2}}\wedge...\wedge
x_{i_{p}}\Big{)}}_{Exp1}\wedge x_{k}\Big{)}\end{split}$ (106)

The same rule is applied to each of the terms in $Exp_{1}$ with the single
term of $Exp_{2}$. At the end, each term of $Exp_{1}$ is composed with all
elements contained in $Exp_{2}$

$\begin{split}&C^{p}(x)\wedge C^{1}(x)=\\\ &\ \ \ \mathbf{x_{1}}\wedge
x_{2}\wedge\ldots\wedge x_{p}\wedge\mathbf{x_{1}}\ \oplus\ \ \
x_{1}\wedge\mathbf{x_{2}}\wedge\ldots\wedge x_{p}\wedge\mathbf{x_{2}}\ \ \
\oplus...\oplus x_{1}\wedge x_{2}\wedge\ldots\wedge
x_{p}\wedge\mathbb{x_{k}}\oplus\\\ &\mathbf{x_{1}}\wedge...\wedge
x_{p-1}\wedge x_{p+1}\wedge\mathbf{x_{1}}\oplus x_{1}\wedge\ldots\wedge
x_{p-1}\wedge x_{p+1}\wedge\mathbb{x_{2}}\oplus...\oplus x_{1}\wedge...\wedge
x_{p+1}\wedge\mathbb{x_{k}}\oplus\\\ &\hskip 199.16928pt\cdots\\\
&x_{k-p}\wedge...\wedge x_{k-1}\wedge x_{k}\wedge\mathbb{x_{1}}\oplus
x_{k-p}\wedge...\wedge x_{k-1}\wedge x_{k}\wedge\mathbb{x_{2}}\oplus...\oplus
x_{k-p}\wedge...\wedge
x_{k-1}\wedge\mathbf{x_{k}}\wedge\mathbf{x_{k}}\end{split}$ (107)

In order to reduce this expression to a unique ANF, it will be necessary first
to remove repetitions of bits in each term. For instance, the first term of
$Exp_{1}$ composed with the first term of $Exp_{2}$ repeats the $x_{1}$ bit.

Afterward, it will be necessary to count the number of times each term does
repeat itself. If a term occurs an odd number of times, it remains and has an
exclusive existence in the ANF; if it occurs an even number of times, it
disappears. In particular, there will be only terms of size $p$, for which the
unique element introduced from $Exp_{2}$ was already part of the term, and the
terms of size $p+1$ for which this term was new. The terms of size $p$ occur
once each time that the new bit is equal to an existing one

$\\#\big{(}\big{|}x_{i}\wedge x_{j}\wedge...\wedge
x_{n}\big{|}=p\big{)}=\binom{p}{1}=p$ (108)

and as $p$ is by definition an even number. This implies that no term of size
$p$ exists in its final ANF, which is consistent with the RHS of Equation
(105).

Finally, to verify the equality, it has to be guaranteed that each element of
RHD of the equation exists and appears an odd number of times in the LHS of
(105). The first condition is verified because all terms of size $p$ exist in
$Exp_{1}$, and the product with $Exp_{2}$ produces all possible combinations
of terms with size $p+1$. It remains to prove that the terms with $p+1$
arguments appear an odd number of times. For that, let us consider a unique
term,

$x_{1}\wedge x_{2}\wedge...\wedge x_{p}\wedge\mathbb{x_{i}},\
i\notin\\{1,2,...,p\\}$ (109)

with $p+1$ different indexes can occur repeatedly due to the composition of
another product term that initially shared $p$ indexes and was composed with
the missing bit. Therefore each term with $p+1$ different bits is created as

$\\#\big{(}\big{|}x_{i}\wedge x_{j}\wedge...\wedge
x_{n}\big{|}=p+1\big{)}=\binom{p+1}{p}=p+1$ (110)

which is an odd number by definition, proving the base case.

Induction step:

$\forall_{y<m+1}\ C^{p}\wedge C^{2^{y}}=C^{p+2^{y}}\implies C^{p}\wedge
C^{2^{m+1}}=C^{p+2^{m+1}}\ ,\ with\ p=\sum_{i\in N}2^{n_{i}},\ \forall_{i\in
N}\ m+1>n_{i}$ (111)

To prove that the RHS of the consequent equality is equal to its LHS, we
rewrite all these functions in the ANF. The procedure is the one used in the
base case resorting to Rule R1 repeatedly. Subsequently, it is necessary to
count the number of times this process creates each term to verify its
inclusion in the ANF. However, this process is more complex for these cases
than for the base case because there are significantly more repetitions, and
the decomposition generates product terms with a mixture of lengths. Once
more, we resort to the symmetry argument to analyze only one product term for
each size. Therefore, we obtain potential terms from the size $2^{m+1}$ to
$2^{m+1}+p$, given that they could repeat from $p$ to $0$ times in the
expression. Furthermore, the number of times each of these terms repeats is
equal to

$\displaystyle\\#\big{(}\big{|}x_{i_{1}}\wedge x_{i_{2}}\wedge...\wedge
x_{i_{p}}\big{|}=2^{m+1}\big{)}=\binom{2^{m+1}}{p}\ repetitions$ (112)
$\displaystyle\\#\big{(}\big{|}x_{i_{1}}\wedge x_{i_{2}}\wedge...\wedge
x_{i_{p}}\wedge\mathbb{x_{j_{1}}}\big{|}=2^{m+1}+1\big{)}=\binom{2^{m+1}}{p-1}*\binom{1}{1}\
repetitions$ (113) $\displaystyle\hskip 142.26378pt\ldots$
$\displaystyle\\#\big{(}\big{|}x_{i_{1}}\wedge x_{i_{2}}\wedge...\wedge
x_{i_{p}}\wedge\mathbb{x_{j_{1}}\wedge...\wedge
x_{j_{q-1}}}\big{|}=2^{m+1}+p-1\big{)}=\binom{2^{m+1}}{1}*\binom{p-1}{p-1}\
repetitions$ (114) $\displaystyle\\#\big{(}\big{|}x_{i_{1}}\wedge
x_{i_{2}}\wedge...\wedge x_{i_{p}}\wedge\mathbb{x_{j_{1}}\wedge...\wedge
x_{j_{q}}}\big{|}=2^{m+1}+p\big{)}=\binom{2^{m+1}}{0}*\binom{p}{0}\
repetitions.$ (115)

It is easy to verify that terms of size $2^{m+1}+p$ exist only once. However,
to verify the equality, it is necessary to prove that all other terms of
smaller dimensions exist an even number of times. In order to achieve that, it
helps to write the modular division by two of these number of combinations
with two additional description presented in [21],

$C^{2^{r}}(x)=\binom{|x|}{2^{r}}\ mod\ 2=Bit^{r}\Big{(}|x|\Big{)}$ (117)

showing that the CSF with a degree equal to a base of two has two equivalent
representations. One as a modular division by two of a combinatorial term
involving the Hamming weight of the input string, and another as a specific
bit $r$ of the binary representation of the Hamming weight $|x|$ which will be
designated $Bit^{r}(|x|)$. With these descriptions and the hypothesis for the
induction step, we obtain that

$\binom{2^{m+1}}{p}\ mod\ 2=\bigwedge_{i\in N}Bit^{n_{i}}(2^{m+1})=0$ (118)

with $p=\sum_{i\in N}2^{n_{i}}$ and as the binary representation of $2^{m+1}$
has only the $(m+1)$th bit equal to $1$, and all other bits and combinations
of bits of the binary representation, smaller than $m+1$, are all equal to
$0$. This proves that the expression in Equation (118) is always zero by the
definition of the number $p$, and therefore the terms of length $2^{m+1}$
vanish. The same argument can be used for all terms of length $2^{m+1}-1$ to
$2^{m+1}+p-1$, as the the modular division by two of their number of
repetitions will be always an even number. This statement holds because

$\binom{2^{m+1}}{\\{1,2,...,p\\}}\ mod\ 2=\bigwedge_{i\in S\subseteq
N}Bit^{n_{i}}(2^{m+1})=0$ (119)

which concludes the proof that all terms of length smaller then $2^{m+1}+p$
vanish, verifying the induction step. ∎

Finally to prove Lemma 1, it is only necessary to obtain the binary
representation of $k$ and, with Lemma 12 compose all the base of two
components of $k$ sequentially in increasing size order.

$\bigg{(}\Big{(}\big{(}C^{2^{i_{1}}}\wedge C^{2^{i_{2}}}\big{)}\wedge
C^{2^{i_{3}}}\Big{)}...\wedge
C^{2^{i_{n}}}\bigg{)}=C^{2^{i_{1}}+2^{i_{2}}+2^{i_{3}}+...+2^{i_{n}}}=C^{k},\
with\ i_{1}<i_{2}<...<i_{n}$ (120)

obtaining exactly the decomposition stated by Lemma 1.

##  Appendix C Proof of Lemma 2

In order to verify that the first instances of the general form presented in
Proposition 1 compute the corresponding CSF for any possible input, it helps
to manipulate the general expression given by Equation (34). The goal is to
rewrite this expression such that it can be expressed in function of the
Hamming weight $\sum_{i=1}^{n}x_{i}=|x|$, which is sufficient to determine the
result of the function, and the size of the input string $n$ that is necessary
to determine the specific polynomial. In particular, the polynomials are
defined, for all ${x\in\\{0,1\\}^{n}}$, as

$\displaystyle\begin{split}\mathsf{poly}_{C^{k}}(x)=\frac{\pi}{2^{k-1}}\Bigg{(}\sum_{j=1}^{k/2}\binom{n-k/2-j}{k/2-j}(-1)^{j}\bigg{(}\sum_{S_{i}\subseteq[n],|S_{i}|=j}\bigoplus_{i\in
S_{i}}x_{i}-\sum_{S_{i}\subseteq[n],|S_{i}|=n-j+1}\bigoplus_{i\in S_{i}}x_{i}\
\bigg{)}\Bigg{)}\ .\end{split}$ (121)

For this transformation, the coefficients remain equal, but the transformed
parity bases ($\bigoplus_{i\in S}x_{i}$) change to a different expression that
evaluates to the same values based on the newly selected parameters,

$\sum_{S_{i}\subseteq[n]\wedge|S_{i}|=j}\bigoplus_{i\in
S_{i}}x_{i}=\sum_{k=0}^{\frac{2j+(-1)^{j}+1}{2}}\binom{|x|}{2k+1}*\binom{n-|x|}{j-2k-1}\
.$ (122)

It will also be useful to distinguish the sum of the transformed parity bases
described with sets of size $n-j+1$, which are defined as

$\displaystyle\sum_{S_{i}\subseteq[n]\wedge|S_{i}|=n-j+1}\bigoplus_{i\in
S_{i}}x_{i}=\left\\{\begin{array}[]{ll}\sum_{l=0}^{\frac{2j+(-1)^{j}+1}{2}}\binom{|x|}{2l+1}*\binom{n-|x|}{j-2l-1},&|x|\
mod\ 2=0\\\
-\sum_{l=0}^{\frac{2j+(-1)^{j}+1}{2}}\binom{|x|}{2l+1}*\binom{n-|x|}{j-2l-2},&|x|\
mod\ 2=1\end{array}\right.\ .$ (125)

Using this transformation and considering the case of $|x|\ mod\ 2=0$, the
general expression in Equation (34) becomes, for all $|x|\in\\{0,2,4,...,n\\}$
and $n\in\mathbb{N}$,

$\displaystyle\begin{split}\mathsf{poly}_{C^{k}}(n,|x|)=\frac{\pi}{2^{k-1}}\Bigg{(}\sum_{j=0}^{k/2}\binom{n-k/2-j}{k/2-j}&(-1)^{j}\Bigg{(}\sum_{l=0}^{\frac{2j+(-1)^{j}+1}{2}}\binom{|x|}{2l+1}*\binom{n-|x|}{j-2l-1}\\\
&-\sum_{l=0}^{\frac{2j+(-1)^{j-1}-1}{2}}\binom{|x|}{2l+1}*\binom{n-|x|}{j-2l-2}\Bigg{)}\Bigg{)}\
.\end{split}$ (126)

For $|x|\ mod\ 2=1$ it can be rewritten for all $|x|\in\\{1,3,5,...,n\\}$ and
$n\in\mathbb{N}$, as

$\displaystyle\begin{split}\mathsf{poly}_{C^{k}}(n,|x|)=\frac{\pi}{2^{k-1}}\Bigg{(}\sum_{j=0}^{k/2}\binom{n-k/2-j}{k/2-j}&(-1)^{j}\Bigg{(}\sum_{l=0}^{\frac{2j+(-1)^{j}+1}{2}}\binom{|x|}{2l+1}*\binom{n-|x|}{j-2l-1}\\\
&+\sum_{l=0}^{\frac{2j+(-1)^{j-1}-1}{2}}\binom{|x|}{2l+1}*\binom{n-|x|}{j-2l-2}\Bigg{)}\Bigg{)}\
.\end{split}$ (127)

Fortunately, with the use of Wolfram Mathematica code we could reduce the
expressions. In particular, it was possible to show that the dependency on $n$
disappears, and the resulting expression is equivalent to

$\mathsf{poly}_{C^{k}}(n,|x|)=\left\\{\begin{array}[]{ll}\frac{\pi}{2^{\frac{k}{2}}*\frac{k}{2}!}\prod_{i=0}^{\frac{k}{2}}(|x|-2i)=\pi*\binom{\frac{|x|}{2}}{\frac{k}{2}},&|x|\
mod\ 2=0\\\
\frac{\pi}{2^{\frac{k}{2}}*\frac{k}{2}!}\prod_{i=0}^{\frac{k}{2}}(|x|-1-2i)=\pi*\binom{\frac{|x|-1}{2}}{\frac{k}{2}},&|x|\
mod\ 2=1\ ,\end{array}\right.$ (128)

with $|x|\in\mathbb{N}$, $n\in\mathbb{N}$, $k=2,4,8,16,32$ and $64$. Now it
remains to show that this simpler expression computes the intended functions,
and for that, we resort again the $Bit^{l}$ notation used in Appendix B

$\mathsf{poly}_{C^{k}}(n,|x|)=\left\\{\begin{array}[]{ll}\binom{\frac{|x|}{2}}{\frac{k}{2}}\
mod\ 2=Bit^{log(k/2)}\big{(}\frac{|x|}{2}\big{)},&|x|\ mod\ 2=0\\\
\binom{\frac{|x|-1}{2}}{\frac{k}{2}}\ mod\
2=Bit^{log(k/2)}\big{(}\frac{|x|-1}{2}\big{)},&|x|\ mod\
2=1\end{array}\right.$ (129)

Knowing that

$Bit^{l}(x)=Bit^{l-1}(x/2)$ (130)

we obtain

$\mathsf{poly}_{C^{k}}(n,h)=\left\\{\begin{array}[]{ll}Bit^{k}\big{(}|x|\big{)},&|x|\
mod\ 2=0\\\ Bit^{k}\big{(}|x|-1\big{)},&|x|\ mod\ 2=1\end{array}\right.$ (131)

Moreover, for any $k>1$ and $|x|\ mod\ 2=1$

$Bit^{k}(|x|-1)=Bit^{k}(|x|)$ (132)

such that

$\displaystyle\mathsf{poly}_{C^{k}}(n,|x|)$
$\displaystyle=Bit^{k}(|x|)=\binom{|x|}{k}mod\ 2=C^{k}(n,|x|)$ (133)
$\displaystyle\equiv C^{k}(x)$ (134)

as intended.

##  Appendix D Proof of Lemma 3

In order to prove the lemma, we will simplify the Fourier transform
sequentially with conversions that do not impact on the computation of the
Fourier coefficients of symmetric semi-Boolean functions until we obtain the
Krawtchouk transform.

First, we will reduce the number of lines in the transform by exploiting a
symmetry between the Fourier coefficients, as stated below.

######  Lemma 13.

All symmetric semi-Boolean functions,
$f_{\ast}:\\{0,1\\}^{n}\rightarrow\mathbb{R}$, have equal Fourier coefficients
$\widehat{f}(S)$ for all the parity bases ($\bigoplus_{l\subseteq S}x_{l}$)
defined by sets with the same size

$S_{i},S_{j}\in[n],\
|S_{i}|=|S_{j}|\implies\widehat{f}(S_{i})=\widehat{f}(S_{j})$ (135)

###### Proof.

The equation used to compute the Fourier coefficient of symmetric semi-Boolean
function can be rewritten using the simplified value vector of the function,

$\displaystyle\widehat{f}(S)$
$\displaystyle=\sum_{x_{i}\in\\{0,1\\}^{n}}f(x_{i})X_{S}(x_{i})$ (136)
$\displaystyle=\sum_{i=0}^{n}v_{f}(i)\sum_{x\in\\{0,1\\}^{n}\wedge|x|=i}X_{S}(x)\
.$ (137)

From this equation, it can be verified that the values of the $v_{f}$ term are
always equal for the same function. Therefore, it is sufficient to show that
for all parity bases defined by sets $S_{i},S_{j}\subseteq[n]$, of the same
size $|S_{i}|=|S_{j}|$, the following equality holds

$\sum_{x\in\\{0,1\\}^{n}\wedge|x|=i}X_{S_{i}}(x)=\sum_{x\in\\{0,1\\}^{n}\wedge|x|=i}X_{S_{j}}(x)\
.$ (138)

This equality is very simple to verify as all the input strings that evaluate
to $1$, one of the parity basis will evaluate to $1$ the other for a specific
permutation ($p$). This permutation has only to exchange the bits of the input
string selected by one of the sets with the bits selected by the other set.
Then for all $x\in\\{0,1\\}^{n}$ and $|x|=i$,

$X_{S_{i}}(x)=X_{S_{j}}(p(x))\ .$ (139)

Furthermore, as no permutation $p$ applied to the input strings changes the
number of strings that are evaluated to $1$ by the parity basis, the sum of
before and after the permutation is exactly equal,

$\sum_{x\in\\{0,1\\}^{n}\wedge|x|=i}X_{S_{j}}(p(x))=\sum_{x\in\\{0,1\\}^{n}\wedge|x|=i}X_{S_{j}}(x)\
.$ (140)

Finally, this proves that equality of Equation $\eqref{eqequal}$ provided one
of the permutations described previously. ∎

This property shows that at most $n+1$ different Fourier coefficients exist,
one for each possible size of the parity bases. Thus, it is sufficient to use
$n+1$ lines of the Fourier transform to determine exactly those values,

$\mathcal{F}^{\prime}=\begin{bmatrix}X_{|S_{i}|=0}(x_{1})&X_{|S_{i}|=0}(x_{2})&X_{|S_{i}|=0}(x_{3})&...&X_{|S_{i}|=0}(x_{2^{n}})\\\
X_{|S_{i}|=1}(x_{1})&X_{|S_{i}|=1}(x_{2})&X_{|S_{i}|=1}(x_{3})&...&X_{|S_{i}|=1}(x_{2^{n}})\\\
X_{|S_{i}|=2}(x_{1})&X_{|S_{i}|=2}(x_{2})&X_{|S_{i}|=2}(x_{3})&...&X_{|S_{i}|=2}(x_{2^{n}})\\\
\vdots&\vdots&\vdots&\ldots&\vdots\\\
X_{|S_{i}|=n}(x_{1})&X_{|S_{i}|=n}(x_{2})&X_{|S_{i}|=n}(x_{3})&...&X_{|S_{i}|=n}(x_{2^{n}})\end{bmatrix}\
.$ (141)

For the second reduction of the transformation matrix, it is necessary to
prove that the Fourier coefficients can be determined based on the simplified
value vector of the function $v_{f}$. Hence, we start with the equation
computing Fourier coefficients using a general line of the Fourier transform
and apply the necessary transformation with some additional simplifications,

$\displaystyle\widehat{f}(S)$
$\displaystyle=\sum_{x_{i}\in\\{0,1\\}^{n}}f(x_{i})X_{S}(x_{i})$ (142)
$\displaystyle=\sum_{i\in\\{0,1\\}^{n}}v_{f}(|x_{i}|)*X_{S}(x_{i})$ (143)
$\displaystyle=\sum_{x^{\prime}\in\\{0,1\\}^{|S|}}\sum_{y^{\prime}\in\\{0,1\\}^{n-|S|}}v_{f}(|x^{\prime}|+|y^{\prime}|)*X_{S}(x^{\prime})$
(144)
$\displaystyle=\sum_{x^{\prime}\in\\{0,1\\}^{|S|}}\sum_{y^{\prime}\in\\{0,1\\}^{n-|S|}}v_{f}(|x^{\prime}|+|y^{\prime}|)*(-1)^{|x^{\prime}|}*\binom{|S|}{|x^{\prime}|}$
(145)
$\displaystyle=\sum_{i=0}^{|S|}\sum_{k=0}^{n-|S|}v_{f}(i+k)*\binom{n-|S|}{k}*(-1)^{i}*\binom{|S|}{i}\
.$ (146)

The resulting equation is already written based on the simplified value vector
and the size of the Fourier basis. However, it is necessary to isolate the
term corresponding to the simplified value vector of the function so that one
can define the elements of a matrix that computes the Fourier coefficients if
applied to that object. For that we resort to the following change of
variables $j=i+k$, yielding

$\displaystyle\widehat{f}(S)$
$\displaystyle=\sum_{i=0}^{|S|}\sum_{j=0}^{n}v_{f}(j)*(-1)^{i}*\binom{|S|}{i}*\binom{n-|S|}{j-i}$
(147)
$\displaystyle=\sum_{j=0}^{n}v_{f}(j)*\sum_{i=0}^{|S|}(-1)^{i}*\binom{|S|}{i}*\binom{n-|S|}{j-i}\
.$ (148)

The last equation allows us to define the lines of a matrix that computes the
Fourier coefficients when applied to the simplified value vector,

$\begin{bmatrix}K_{1,1}&K_{1,2}&K_{1,3}&...&K_{1,n+1}\\\
K_{2,1}&K_{2,2}&K_{2,3}&...&K_{2,n+1}\\\
K_{3,1}&K_{3,2}&K_{3,3}&...&K_{3,n+1}\\\ \vdots&\vdots&\vdots&\ldots&\vdots\\\
K_{n+1,1}&K_{n+1,2}&K_{n+1,3}&...&K_{n+1,n+1}\end{bmatrix}*\begin{bmatrix}v_{f}(0)\\\
v_{f}(1)\\\ v_{f}(2)\\\ \vdots\\\ v_{f}(n)\end{bmatrix}\\\
=\begin{bmatrix}\widehat{f}(|S|=0)\\\ \widehat{f}(|S|=1)\\\
\widehat{f}(|S|=2)\\\ \vdots\\\ \widehat{f}(|S|=n)\\\ \end{bmatrix}\ ,$ (149)

with the following rule defining the entries of the matrix for the resulting
transformation,

$K_{i,j}=\sum_{k=0}^{j}(-1)^{k}\binom{j}{k}\binom{n-j}{i-k}\ .$ (150)

The rule obtained for each matrix element is precisely the rule used to build
the Krawtchouk transformation, proving that one can compute the Fourier
coefficient with this transformation.

In the end, to prove the bound on the number of operations, it is necessary to
determine the number of operations necessary to build the matrix. In
particular, each element results from the sum of combinatorial terms, which
compute factorial terms. These can be exponentially bigger than $n$.
Nevertheless, they have at most $n^{2}$ digits, which are numbers that are
simple to operate with for efficient number multiplication algorithms. The
latter are bounded by $\mathcal{O}\big{(}n\ log(n)\big{)}$. Therefore, the
operations necessary to compute each element of the Krawtchok transform are
bounded by $\mathcal{O}(n^{3})$. Then, these are computed for all matrix
elements, which pushes the upper bound to $\mathcal{O}(n^{5})$.

##  Appendix E NMQC⊕ measurement assignment of a CSF: An Example

The complete symmetric function $C^{5}:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ is
defined, for all $x\in\\{0,1\\}^{n}$, as

$C^{5}(x)=\bigoplus_{i_{1}=1}^{n-4}x_{i_{1}}\bigg{(}\bigoplus_{i_{2}=i_{1}+1}^{n-3}x_{i_{2}}\bigg{(}\bigoplus_{i_{3}=i_{2}+1}^{n-2}x_{i_{3}}\bigg{(}\bigoplus_{i_{4}=i_{3}+1}^{n-1}x_{i_{4}}\bigg{(}\bigoplus_{i_{5}=i_{4}+1}^{n}x_{i_{4}}\bigg{)}\bigg{)}\bigg{)}\bigg{)}\
.$ (151)

This can be decomposed as the conjunction of two CSF with a degree equal to a
power of two as:

$C^{5}(x)=C^{4}(x)\wedge
C^{1}(x)=\bigoplus_{i_{1}=1}^{n-3}x_{i_{1}}\bigg{(}\bigoplus_{i_{2}=i_{1}+1}^{n-2}x_{i_{2}}\bigg{(}\bigoplus_{i_{3}=i_{2}+1}^{n-1}x_{i_{3}}\bigg{(}\bigoplus_{i_{4}=i_{3}+1}^{n}x_{i_{4}}\bigg{)}\bigg{)}\bigg{)}\bigg{(}\bigoplus_{j=0}^{n}x_{j}\bigg{)}\
.$ (152)

Now resorting to the multi-linear polynomials from Lemma 2 and Proposition 1,
one can translate this family of Boolean functions can be rephrased as the
following family of multi-linear polynomials,

$\displaystyle\mathsf{poly}_{C^{5}}(x)=$
$\displaystyle\frac{\pi}{32}\bigg{(}\frac{(n-4)(n-3)}{2}\Big{(}1-\prod_{j=0}^{n}x_{j}\Big{)}-(n-4)\Big{(}\sum_{i=0}^{n}x_{i}+\sum_{i=0}^{n}\Big{(}\big{(}\prod_{j=0}^{n}x_{j}\big{)}*x_{i}\Big{)}\Big{)}$
(153)
$\displaystyle+\Big{(}\sum_{i=0}^{n}\sum_{j=i}^{n}x_{i}*x_{j}\Big{)}\Big{)}-\Big{(}\sum_{i=0}^{n}\sum_{j=i}^{n}\big{(}\prod_{j=0}^{n}x_{j}\big{)}*x_{i}*x_{j}\Big{)}\bigg{)}\
.$ (154)

Let us consider a specific instance of this family with a fixed size for the
input strings ($|x|=6$) such that the following polynomial represents the
function,

$\displaystyle\mathsf{poly}_{C^{5}}(x)=$
$\displaystyle\frac{\pi}{32}\Big{(}3-3*\prod_{j=0}^{6}x_{j}-2\sum_{i=0}^{6}x_{i}+2\sum_{i=0}^{6}\Big{(}\big{(}\prod_{j=0}^{6}x_{j}\big{)}*x_{i}\Big{)}$
(155)
$\displaystyle+\Big{(}\sum_{i=0}^{6}\sum_{j=i}^{6}x_{i}*x_{j}\Big{)}\Big{)}-\Big{(}\sum_{i=0}^{6}\sum_{j=i}^{6}\big{(}\prod_{j=0}^{6}x_{j}\big{)}*x_{i}*x_{j}\Big{)}\Big{)}\
.$ (156)

This multi-linear polynomial translates to a measurement assignment with a
43-qubit GHZ state, $\ket{\Psi_{GHZ}^{43}}=1/\sqrt{2}\big{(}\ket{0}^{\otimes
43}+\ket{1}^{\otimes 43}\big{)}$, with the following linear functions and
measurement operators

$\displaystyle L_{i\in\\{1,..,6\\}}$ $\displaystyle\equiv x_{j},\ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \ with\
M_{i}(s_{i})=\cos(\frac{\pi}{8}*s_{i})\sigma_{x}+\sin(\frac{\pi}{8}*s_{i})\sigma_{y}$
(157) $\displaystyle L_{i\in\\{7,..,12\\}}$ $\displaystyle\equiv
x_{j}\oplus\bigoplus_{k=1}^{6}x_{k},\ \ \ \ \ \ \ with\
M_{i}(s_{i})=\cos(-\frac{\pi}{8}*s_{i})\sigma_{x}+\sin(-\frac{\pi}{8}*s_{i})\sigma_{y}$
(158) $\displaystyle L_{i\in\\{13,..,27\\}}$ $\displaystyle\equiv x_{j}\oplus
x_{l},\ \ \ \ \ \ \ \ \ \ \ \ \ with\
M_{i}(s_{i})=\cos(-\frac{\pi}{16}*s_{i})\sigma_{x}+\sin(-\frac{\pi}{16}*s_{i})\sigma_{y}$
(159) $\displaystyle L_{i\in\\{28,..,42\\}}$ $\displaystyle\equiv x_{j}\oplus
x_{l}\oplus\bigoplus_{k=1}^{6}x_{k},\ with\
M_{i}(s_{i})=\cos(\frac{\pi}{16}*s_{i})\sigma_{x}+\sin(\frac{\pi}{16}*s_{i})\sigma_{y}$
(160) $\displaystyle L_{43}$ $\displaystyle\equiv\bigoplus_{k=1}^{6}x_{k},\ \
\ \ \ \ \ \ \ \ \ \ \ \ with\
M_{i}(s_{i})=\cos(\frac{3\pi}{16}*s_{i})\sigma_{x}+\sin(\frac{3\pi}{16}*s_{i})\sigma_{y}\
,$ (161)

for which the linear functions are defined as a general instance, and the
specific linear functions are all the combinations of this expression built
with the $6$ inputs bits of the input string. The second best solution
regarding resource requirements is the solution presented in [22], which
requires $63$ qubits. In particular, this solution would require all the
linear functions of the form $x_{i}\oplus x_{j}\oplus x_{k}$, which become
unnecessary in the presented solution.

##  Appendix F Proof of Lemma 7

We will prove the lemma introducing a more detailed description of the problem
and the algorithm to solve it. In the end, the algorithm’s running time is
shown to be polynomially bounded.

The algorithm has to determine whether there exits a symmetric multi-linear
polynomial with a particular set of non-zero Fourier coefficients,
$F=\big{\\{}\widehat{f}(|S|=i)\ \big{|}\ i\in T,\ T\subseteq[n]\big{\\}}$,
that computes deterministically the SBF. Therefore, if this polynomial exists
it will be an element of the set of multi-linear polynomials equivalent to the
SBF in the NMQC⊕ model. Thus, it will be helpful to redefine this set in in a
similar way to what we have done previously for the minimal sparsity in
Definition 15. First, consider that any semi-Boolean function
$g:\\{0,1\\}^{n}\rightarrow\mathbb{Z}$ that verifies the following equality,

$g(x)=f(x)+2h(x)\ ,$ (162)

for any other semi-Boolean function $h(x):\\{0,1\\}^{n}\rightarrow\mathbb{Z}$,
has a multi-linear polynomial that computes the Boolean function
$f(x):\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ deterministically in the NMQC⊕ model.
This allows us to use the semi-Boolean function $h(x)$ as the degree of
freedom that determines the elements of the equivalence set. Furthermore this
degree of freedom can be restricted for our specific problem. First, only
symmetric multi-linear polynomials are considered. Therefore if $f(x)$ is
symmetric, then also $h(x)$ has to be symmetric to generate symmetric semi-
Boolean functions equivalent to $f(x)$ through Equation (162). In addition,
the same equality on the functions will be true for the corresponding multi-
linear polynomials. Therefore, the elements of the set of symmetric multi-
linear polynomials $\mathsf{poly}_{g(x)}$ equivalent to the symmetric Boolean
function $f(x)$ in the NMQC⊕ model, must verify the following equality,

$\sum_{i=0}^{n}\widehat{g}\big{(}|S|=i\big{)}=\sum_{i=0}^{n}\widehat{f}\big{(}|S|=i\big{)}+2\sum_{i=0}^{n}\widehat{h}\big{(}|S|=i\big{)}\
.$ (163)

A second restriction imposed by the problem is that only a specific subset of
Fourier coefficients $T\subseteq[n]$ can be non-zero. Therefore all other
Fourier coefficients of the symmetric multi-linear polynomial have to be equal
to zero. This implies that all the valid symmetric multi-linear polynomials
correspond respectively to instances of $h(x)$ that verify simultaneously the
following equality $\widehat{f}(|S|=i)=-2\widehat{h}(|S|=i)$ for all $i\in E$,
with $E=[n]\setminus T$. This guarantees that $\widehat{g}(|S|=i)$ is equal to
zero for all $i\in E$. Finally, a solution to the problem exists if there is a
semi-Boolean function $h(x)$ for which the following equation is verified,

$\sum_{x}X_{|S|=i}(x)f(x)=-\sum_{x}X_{|S|=i}(x)2h(x)$ (164)

for all $i\in E$. This problem defines a system of linear Diophantine
equations. Therefore, determining if a symmetric measurement assignment exists
reduces to determining if this system of linear Diophantine equations has a
solution. Thus, a solution to the decision problem will always exist. However,
we should define if it can be determined in polynomial time with respect to
the size of the function. Unfortunately, the equations are of exponential size
in relation to the input string because they represent specific lines of the
Fourier transform. Therefore, any algorithm that receive these equations as
input will need to manipulate an exponential size object. This means that
solving the problem would also take exponential time.

Fortunately, the problem can be simplified using the Krawtchouk transform
which computes the Fourier coefficient using equations of polynomial size. All
the Fourier coefficients will be determined using specific lines of the
Krawtchouk transform applied to the simplified value vectors of the functions
$f$ and $h$, designated $v_{f}$ and $v_{h}$. Consequently, the problem reduces
to finding a solution to the following equation,

$\sum_{j=0}^{n}K_{i,j}^{[n]}*v_{f}(j)=-\sum_{j=0}^{n}K_{i,j}^{[n]}*2*v_{h}(j)$
(165)

for all $i\in E$. The combination of all these equations defines a system of
Diophantine equations that can be represented as,

$\begin{bmatrix}K_{i_{1},1}&K_{i_{1},2}&K_{i_{1},3}&...&K_{i_{1},n+1}\\\
K_{i_{2},1}&K_{i_{2},2}&K_{i_{2},3}&...&K_{i_{2},n+1}\\\
K_{i_{3},1}&K_{i_{3},2}&K_{i_{3},3}&...&K_{i_{3},n+1}\\\
\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\\
K_{i_{k},1}&K_{i_{k},2}&K_{i_{k},3}&...&K_{i_{k},n+1}\\\
\end{bmatrix}*2\begin{bmatrix}v_{h}(0)\\\ v_{h}(2)\\\ v_{h}(3)\\\ \vdots\\\
v_{h}(n)\end{bmatrix}\\\ =\begin{bmatrix}\widehat{f}(|S|=i_{1})\\\
\widehat{f}(|S|=i_{2})\\\ \widehat{f}(|S|=i_{3})\\\ \vdots\\\
\widehat{f}(|S|=i_{k})\\\ \end{bmatrix}\ .$ (166)

In order to verify if a system of Diophantine equations has a solution, one
can use the Smith Normal Form of the matrix defining the system [120]. In
particular, the matrix defining the system of Diophantine equations required
to be solved will be the submatrix of the Krawtchouk transform composed of the
lines selected by the set $E$, $\mathcal{K}^{[n+1]}[E;1,2,...,n+1]$.
Therefore, the Smith Normal Form of this matrix creates three unique matrices
that verify the following equality,

$U^{-1}DV^{-1}=\mathcal{K}^{[n]}[E;1,2,...,n+1]\ .$ (167)

Then the system of equations to be solved can be decomposed as,

$\displaystyle U^{-1}DV^{-1}*v_{h}[E]$ $\displaystyle=[\widehat{f}(E)]$ (168)
$\displaystyle U^{-1}DV^{-1}*2*v_{h}^{\prime}[E]$
$\displaystyle=[\widehat{f}(E)]$ (169) $\displaystyle
V^{-1}*v_{h}^{\prime}[E]=\frac{D^{-1}U[\widehat{f}(E)]}{2}$ (170)

with $[f\widehat{(E)}]$ being the set of Fourier coefficients selected by $E$,
resulting from $T$. Consequently, a solution for the system exists if for all
$i\in E$,

$\frac{(U[\widehat{f}(|S|=i)])}{2D[i,i]}\in\mathbb{Z}\ .$ (171)

Finally, to prove that this process can be performed in polynomial time, it
will be necessary to show that each step is polynomially bound. First, the
Smith decomposition can be performed with algorithms that scale polynomially
concerning the size of the matrix, as proven in [121]. This solution
demonstrates that determining the Smith Normal Form of the Krawtchouk
transform can be done in polynomial time and space, given that the matrix
scales polynomially with the size of the input string. Then, all the matrix
and vector multiplications are polynomially bounded, provided these objects
are of polynomial size [122]. The last process tests if all elements of the
final vector, composed of the elements described by Equation (171), are
integer numbers. The previously mentioned vector is smaller or equal to $n$,
which also makes this subprocess polynomially bounded. Therefore, the entire
process is polynomially bounded, proving the lemma.

##  Appendix G Support for Conjecture 2

The conjecture is supported by the numerical verification process described
below. First, the polynomially scaling algorithm described in the proof of
Lemma 7 was implemented, in a way such that one could test the order of
magnitude upon whether a solution exists or not. This was necessary because
the number of combinations of Fourier coefficients that can be selected to be
tested grows exponentially. However, applying the algorithm to a subset of
these combinations suffices to test the scaling rate. The last statement is
supported by the number of parity bases corresponding to each non-zero Fourier
coefficient. Moreover, a non-zero Fourier coefficient relative to parity bases
of size $t=|S|$ imposes the use of $\binom{n}{|S|}$ qubits and measurements.
Therefore, each Fourier coefficient is related to a certain asymptotic growth
rate,

$\overbrace{\underbrace{\binom{n}{0}}_{1}}^{\widehat{f}({|S|=0})},\
\overbrace{\underbrace{\binom{n}{1}}_{n}}^{\widehat{f}({|S|=1})},\
\overbrace{\underbrace{\binom{n}{2}}_{\mathcal{O}\big{(}n^{2}\big{)}}}^{\widehat{f}({|S|=2})},\
\overbrace{\underbrace{\binom{n}{3}}_{\mathcal{O}\big{(}n^{3}\big{)}}}^{\widehat{f}({|S|=3})},\
\ \ \ \ldots\ \ \ \
,\overbrace{\underbrace{\binom{n}{n-2}}_{\mathcal{O}\big{(}n^{2}\big{)}}}^{\widehat{f}({|S|=n-2})},\
\overbrace{\underbrace{\binom{n}{n-1}}_{n}}^{\widehat{f}({|S|=n-1})},\
\overbrace{\underbrace{\binom{n}{n}}_{1}}^{\widehat{f}({|S|=n})}\ .$ (172)

In order to test if there is a solution that has at most a certain growth rate
$\mathcal{O}(n^{t})$, it is sufficient to test if all the Fourier coefficients
with larger growth rates could be made equal to zero. Therefore, this method
reduced the number of necessary tests necessary to determine the order of the
growth rate to a maximum of $n/2$ for each symmetric function. In particular,
for the conjecture it was enough to test if there are solutions with a growth
rate of $\mathcal{O}(n^{\mathsf{deg}(f)/2}-1)$ and
$\mathcal{O}(n^{\mathsf{deg}(f)/2})$. Therefore, all Fourier coefficients with
larger scaling rates than these values must be zero for a positive answer.
This statement implies that the following equation

$\sum_{j=0}^{n}K_{i,j}^{[n]}*v_{f}(j)=-\sum_{j=0}^{n}K_{i,j}^{[n]}*2*v_{h}(j)$
(173)

with $[n]$ defining the size and $i,j$ the element of the Krawtchouk
transform, is verified for all $\\{i\big{|}\ i>\mathsf{deg}(f),\
i>n-\mathsf{deg}(f)/2\\}$ if the function has a scaling rate of
$\mathcal{O}(n^{\mathsf{deg(f)/2-1}})$. Equivalently, for
$\mathcal{O}(n^{\mathsf{deg(f)/2}})$ the same equation has to be true for all
$\\{i\big{|}\ i>\mathsf{deg}(f)+1,\ i>n-\mathsf{deg}(f)/2-1\\}$.

The numerical tests realized verified that all complete symmetric functions
that can be defined with an input size up to 345 bits have solutions with the
respective sparsities scaling with $\mathcal{O}(n^{\mathsf{deg(f)/2}})$ and
failed to have a solution with $\mathcal{O}(n^{\mathsf{deg(f)/2-1}})$.
Moreover, the main limitation of the numerical process is that for each
specific CSF, only instances of a particular size of the input string are
tested each time. One can not use this test to verify the sparsities of all
possible input strings of a particular CSF simultaneously.

In summary, a reasonable number of functions have verified the conjectured
scaling relating to their minimum sparsity. Furthermore, the same conjecture
and numerical test are consistent with the lower bound found for two
particular symmetric Boolean functions. More numerical tests could be
conducted. We believe that actually proving the conjecture will be possible
resorting to a general Smith decomposition of the Krawtchouk transform.