{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T01:41:34Z","timestamp":1760146894415,"version":"build-2065373602"},"reference-count":46,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2024,12,31]],"date-time":"2024-12-31T00:00:00Z","timestamp":1735603200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Australian Research Council Centre of Excellence for Engineered Quantum Systems","award":["CE170100009","20201969"],"award-info":[{"award-number":["CE170100009","20201969"]}]},{"name":"Sydney Quantum Academy, Sydney, NSW, Australia","award":["CE170100009","20201969"],"award-info":[{"award-number":["CE170100009","20201969"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>The density classification (DC) task, a computation which maps global density information to local density, is studied using one-dimensional non-unitary quantum cellular automata (QCAs). Two approaches are considered: one that preserves the number density and one that performs majority voting. For number-preserving DC, two QCAs are introduced that reach the fixed-point solution in a time scaling quadratically with the system size. One of the QCAs is based on a known classical probabilistic cellular automaton which has been studied in the context of DC. The second is a new quantum model that is designed to demonstrate additional quantum features and is restricted to only two-body interactions. Both can be generated by continuous-time Lindblad dynamics. A third QCA is a hybrid rule defined by both discrete-time and continuous-time three-body interactions that is shown to solve the majority voting problem within a time that scales linearly with the system size.<\/jats:p>","DOI":"10.3390\/e27010026","type":"journal-article","created":{"date-parts":[[2024,12,31]],"date-time":"2024-12-31T10:17:40Z","timestamp":1735640260000},"page":"26","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Density Classification with Non-Unitary Quantum Cellular Automata"],"prefix":"10.3390","volume":"27","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7350-5286","authenticated-orcid":false,"given":"Elisabeth","family":"Wagner","sequence":"first","affiliation":[{"name":"School of Mathematical and Physical Sciences, Macquarie University, Sydney, NSW 2109, Australia"},{"name":"Australian Research Council Centre of Excellence in Engineered Quantum Systems, Macquarie University, Sydney, NSW 2109, Australia"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-7514-0075","authenticated-orcid":false,"given":"Federico","family":"Dell\u2019Anna","sequence":"additional","affiliation":[{"name":"Dipartimento di Fisica e Astronomia, Universit\u00e0 di Bologna, I-40127 Bologna, Italy"},{"name":"Istituto Nazionale di Fisica Nucleare, Sezione di Bologna, I-40127 Bologna, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2577-6561","authenticated-orcid":false,"given":"Ramil","family":"Nigmatullin","sequence":"additional","affiliation":[{"name":"School of Mathematical and Physical Sciences, Macquarie University, Sydney, NSW 2109, Australia"},{"name":"Quantinuum, 13-15 Hills Road, Cambridge CB2 1NL, UK"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6019-966X","authenticated-orcid":false,"given":"Gavin","family":"K. Brennen","sequence":"additional","affiliation":[{"name":"School of Mathematical and Physical Sciences, Macquarie University, Sydney, NSW 2109, Australia"},{"name":"Australian Research Council Centre of Excellence in Engineered Quantum Systems, Macquarie University, Sydney, NSW 2109, Australia"}]}],"member":"1968","published-online":{"date-parts":[[2024,12,31]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"066106","DOI":"10.1103\/PhysRevE.66.066106","article-title":"Nondeterministic density classification with diffusive probabilistic cellular automata","volume":"66","year":"2002","journal-title":"Phys. Rev. E"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"133074","DOI":"10.1016\/j.physd.2021.133074","article-title":"Progress, gaps and obstacles in the classification of cellular automata","volume":"432","author":"Vispoel","year":"2022","journal-title":"Phys. D Nonlinear Phenom."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Laboudi, Z. (2019, January 22\u201325). An Effective Approach for Solving the Density Classification Task by Cellular Automata. Proceedings of the 2019 4th World Conference on Complex Systems (WCCS), Ouarzazate, Morocco.","DOI":"10.1109\/ICoCS.2019.8930805"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"669","DOI":"10.25088\/ComplexSystems.29.3.669","article-title":"Efficient Solutions of the Density Classification Task in One-Dimensional Cellular Automata: Where Can They Be Found?","volume":"29","author":"Laboudi","year":"2020","journal-title":"Complex Syst."},{"key":"ref_5","first-page":"92","article-title":"One-dimensional Uniform Arrays that Wash out Finite Islands","volume":"14","author":"Gacs","year":"1978","journal-title":"Probl. Peredachi Informatsii"},{"key":"ref_6","unstructured":"Mitchell, M., Hraber, P., and Crutchfield, J.P. (1993). Revisiting the Edge of Chaos: Evolving Cellular Automata to Perform Computations. arXiv."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"5148","DOI":"10.1103\/PhysRevLett.74.5148","article-title":"No Perfect Two-State Cellular Automata for Density Classification Exists","volume":"74","author":"Land","year":"1995","journal-title":"Phys. Rev. Lett."},{"key":"ref_8","first-page":"1","article-title":"Density classification on infinite lattices and trees","volume":"18","author":"Mairesse","year":"2013","journal-title":"Electron. J. Probab."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"899","DOI":"10.1142\/S0129183198000868","article-title":"A Simple Cellular Automaton that Solves the Density and Ordering Problems","volume":"9","author":"Sipper","year":"1998","journal-title":"Int. J. Mod. Phys. C"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"4969","DOI":"10.1103\/PhysRevLett.77.4969","article-title":"Two-state, r0ex0ex=0ex0ex1 Cellular Automaton that Classifies Density","volume":"77","author":"Capcarrere","year":"1996","journal-title":"Phys. Rev. Lett."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"R2081","DOI":"10.1103\/PhysRevE.55.R2081","article-title":"Solution of the density classification problem with two cellular automata rules","volume":"55","year":"1997","journal-title":"Phys. Rev. E"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"75","DOI":"10.5506\/APhysPolBSupp.12.75","article-title":"Explorations of Ternary Cellular Automata and Ternary Density Classification Problems","volume":"12","author":"Procyk","year":"2019","journal-title":"Acta Phys. Pol. B Proc. Suppl."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1007\/s00224-012-9386-3","article-title":"Stochastic Cellular Automata Solutions to the Density Classification Problem","volume":"53","year":"2013","journal-title":"Theory Comput. Syst."},{"key":"ref_14","first-page":"289","article-title":"Very Effective Evolutionary Techniques for Searching Cellular Automata Rule Spaces","volume":"3","author":"Wolz","year":"2008","journal-title":"J. Cell. Autom."},{"key":"ref_15","first-page":"357","article-title":"On Density Determination With Cellular Automata: Results, Constructions and Directions","volume":"9","year":"2014","journal-title":"J. Cell. Autom."},{"key":"ref_16","unstructured":"Schumacher, B., and Werner, R.F. (2004). Reversible quantum cellular automata. arXiv."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"042311","DOI":"10.1103\/PhysRevA.68.042311","article-title":"Entanglement dynamics in one-dimensional quantum cellular automata","volume":"68","author":"Brennen","year":"2003","journal-title":"Phys. Rev. A"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s11128-018-1983-x","article-title":"Quantum walks via quantum cellular automata","volume":"17","author":"Costa","year":"2018","journal-title":"Quantum Inf. Process."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"070503","DOI":"10.1103\/PhysRevLett.124.070503","article-title":"Unitary and Nonunitary Quantum Cellular Automata with Rydberg Arrays","volume":"124","author":"Wintermantel","year":"2020","journal-title":"Phys. Rev. Lett."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"150601","DOI":"10.1103\/PhysRevLett.133.150601","article-title":"Quantum cellular automata for quantum error correction and density classification","volume":"133","author":"Guedes","year":"2024","journal-title":"Phys. Rev. Lett."},{"key":"ref_21","unstructured":"Liu, A., Han, Q., Xia, L., and Yu, N. (August, January 31). Accelerating Voting by Quantum Computation. Proceedings of the Uncertainty in Artificial Intelligence, Pittsburgh, PA, USA."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Sun, X., Su, X., and Bian, X. (2024, October 28). Quantum Vote Based on Quantum Logical Operators. Available online: https:\/\/ssrn.com\/abstract=4686153.","DOI":"10.2139\/ssrn.4686153"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Andronikos, T., and Stefanidakis, M. (2022). A Two-Party Quantum Parliament. Algorithms, 15.","DOI":"10.3390\/a15020062"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1007\/s11128-021-03048-6","article-title":"A quantum voting protocol using single-particle states","volume":"20","author":"Li","year":"2021","journal-title":"Quantum Inf. Process."},{"key":"ref_25","unstructured":"Zhong, W., Ke, Y., Wang, Y., Chen, Y., Chen, J., and Ma, P. (2021). Best Subset Selection: Statistical Computing Meets Quantum Computing. arXiv."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"062306","DOI":"10.1103\/PhysRevA.95.062306","article-title":"Quantum voting and violation of Arrow\u2019s impossibility theorem","volume":"95","author":"Bao","year":"2017","journal-title":"Phys. Rev. A"},{"key":"ref_27","unstructured":"Buhrman, H., Linden, N., Man\u010dinska, L., Montanaro, A., and Ozols, M. (2022). Quantum majority vote. arXiv."},{"key":"ref_28","unstructured":"Gilchrist, A., Terno, D.R., and Wood, C.J. (2011). Vectorization of quantum operations and its use. arXiv."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"802","DOI":"10.1038\/299802a0","article-title":"A single quantum cannot be cloned","volume":"299","author":"Wootters","year":"1982","journal-title":"Nature"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1103\/PhysRevLett.53.311","article-title":"Equivalence of Cellular Automata to Ising Models and Directed Percolation","volume":"53","author":"Domany","year":"1984","journal-title":"Phys. Rev. Lett."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"02LT02","DOI":"10.1088\/2058-9565\/aaf831","article-title":"Non-equilibrium absorbing state phase transitions in discrete-time quantum cellular automaton dynamics on spin lattices","volume":"4","author":"Lesanovsky","year":"2019","journal-title":"Quantum Sci. Technol."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"100403","DOI":"10.1103\/PhysRevLett.125.100403","article-title":"Nonequilibrium Phase Transitions in (1+1)-Dimensional Quantum Cellular Automata with Controllable Quantum Correlations","volume":"125","author":"Gillman","year":"2020","journal-title":"Phys. Rev. Lett."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"230502","DOI":"10.1103\/PhysRevLett.127.230502","article-title":"Quantum and Classical Temporal Correlations in (1+1)D Quantum Cellular Automata","volume":"127","author":"Gillman","year":"2021","journal-title":"Phys. Rev. Lett."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"L040201","DOI":"10.1103\/PhysRevA.103.L040201","article-title":"Numerical simulation of quantum nonequilibrium phase transitions without finite-size effects","volume":"103","author":"Gillman","year":"2021","journal-title":"Phys. Rev. A"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"043167","DOI":"10.1103\/PhysRevResearch.3.043167","article-title":"Directed percolation in non-unitary quantum cellular automata","volume":"3","author":"Nigmatullin","year":"2021","journal-title":"Phys. Rev. Res."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"2863","DOI":"10.1103\/PhysRevLett.69.2863","article-title":"Density matrix formulation for quantum renormalization groups","volume":"69","author":"White","year":"1992","journal-title":"Phys. Rev. Lett."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"070601","DOI":"10.1103\/PhysRevLett.107.070601","article-title":"Time-dependent variational principle for quantum lattices","volume":"107","author":"Haegeman","year":"2011","journal-title":"Phys. Rev. Lett."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"165116","DOI":"10.1103\/PhysRevB.94.165116","article-title":"Unifying time evolution and optimization with matrix product states","volume":"94","author":"Haegeman","year":"2016","journal-title":"Phys. Rev. B"},{"key":"ref_39","first-page":"r0.3","article-title":"Codebase release 0.3 for ITensor","volume":"4","author":"Fishman","year":"2022","journal-title":"SciPost Phys. Codebases"},{"key":"ref_40","unstructured":"Boykin, P., Roychowdhury, C., Mor, T., and Vatan, F. (July, January 28). Fault tolerant computation on ensemble quantum computers. Proceedings of the International Conference on Dependable Systems and Networks, Florence, Italy."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"010333","DOI":"10.1103\/PRXQuantum.5.010333","article-title":"Measurement-Free Fault-Tolerant Quantum Error Correction in Near-Term Devices","volume":"5","author":"Locher","year":"2024","journal-title":"PRX Quantum"},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"100501","DOI":"10.1103\/PhysRevLett.105.100501","article-title":"Fault Tolerance with Noisy and Slow Measurements and Preparation","volume":"105","author":"Brennen","year":"2010","journal-title":"Phys. Rev. Lett."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1146\/annurev-physchem-050317-021219","article-title":"Exploring Energy Landscapes","volume":"69","author":"Wales","year":"2018","journal-title":"Annu. Rev. Phys. Chem."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"5111","DOI":"10.1021\/jp970984n","article-title":"Global Optimization by Basin-Hopping and the Lowest Energy Structures of Lennard-Jones Clusters Containing up to 110 Atoms","volume":"101","author":"Wales","year":"1997","journal-title":"J. Phys. Chem. A"},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1038\/s41592-019-0686-2","article-title":"SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python","volume":"17","author":"Virtanen","year":"2020","journal-title":"Nat. Methods"},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"1760","DOI":"10.1016\/j.cpc.2012.02.021","article-title":"QuTiP: An open-source Python framework for the dynamics of open quantum systems","volume":"183","author":"Johansson","year":"2012","journal-title":"Comput. Phys. Commun."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/27\/1\/26\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T16:58:13Z","timestamp":1760115493000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/27\/1\/26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,31]]},"references-count":46,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2025,1]]}},"alternative-id":["e27010026"],"URL":"https:\/\/doi.org\/10.3390\/e27010026","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2024,12,31]]}}}