Submit to Entropy Review for Entropy Propose a Special Issue

Journal Menu

Journal Browser

► Journal Browser

Exploring the NP-Complexity of Nature: Critical Phenomena, Chaos, Fractals, Graphs, Boson Sampling, Quantum Computing and More

Print Special Issue Flyer
Special Issue Editors
Special Issue Information
Keywords
Benefits of Publishing in a Special Issue
Published Papers

A special issue of Entropy (ISSN 1099-4300). This special issue belongs to the section "Complexity".

Deadline for manuscript submissions: closed (31 December 2020) | Viewed by 23195

Share This Special Issue

Special Issue Editor

Prof. Dr. Vitaly Kocharovsky

E-Mail Website
Guest Editor

Department of Physics and Astronomy, Texas A&M University, College Station, TX 77843-4242, USA
Interests: quantum fundamentals; quantum optics; critical phenomena; phase transitions; electromagnetic waves

Special Issue Information

Dear Colleagues,

Tremendous recent progress in informational, computational, and quantum technologies has brought complex systems whose functionality is directly based on their NP/#P-complexity to the frontiers of modern science, research, and engineering. The examples are various quantum many-body systems for quantum computing aimed at demonstrating supremacy over classical computers in solving the problems that require an exponentially large number of operations. One such problem is boson sampling. Many other examples emerge in material science, condensed matter, and nuclear physics. In particular, they include various mesoscopic systems with unusual properties determined by the cooperative, topological, or critical phenomena. The basic models of the phase transitions in the statistical physics, such as the Ising and monomer-dimer models, directly address the NP/#P-complexity of the critical phenomena. The protocols and models employed in modern communications and cryptography, as well as the mathematical objects/models in the graph theory, theory of fractals and chaos, number theory, and combinatorics also have an intimate connection with the NP- and #P-complete problems of computational complexity theory. An example of the latter is a matrix permanent computing of which was the first counting problem proven to be #P-complete and yet corresponded to an easy, linear-time polynomial problem in accepting paths. Remarkably, the graph theory and the Markov chain Monte Carlo method recently provided a fully polynomial randomized approximation scheme (FPRAS) for numerical computation of the permanent of nonnegative matrices and the ferromagnetic Ising model. Machine learning and artificial intelligence techniques constitute an alternative, rapidly progressing way of addressing NP/#P-complex problems.

The modern stage in the development of the broad multidisciplinary area of research outlined above is characterized by a transition from the abstract general analysis and schemes to the invention, design, implementation, and application of the real NP/#P-complexity-based systems.

This Special Issue presents this recent advance in the theory of the NP/#P-complexity of nature, finding new models and systems that demonstrate or implement the NP/#P-complexity, developing analytic and computational methods for the analysis of such systems, as well as establishing connections and analogies between different complex systems. We welcome multidisciplinary NP/#P-complexity related papers—from papers devoted to the pure mathematics of the NP/#P-complex objects/models and computational/approximation methods and algorithms, including the ones based on the machine learning and artificial intelligence techniques, to papers addressing the particular NP/#P-complex features of the actual systems in physics, chemistry, biology, material science, engineering, communication technologies, cryptography, quantum and classical computing, statistics, social sciences and more.

Prof. Vitaly Kocharovsky
Guest Editor

Manuscript Submission Information

Manuscripts should be submitted online at www.mdpi.com by registering and logging in to this website. Once you are registered, click here to go to the submission form. Manuscripts can be submitted until the deadline. All submissions that pass pre-check are peer-reviewed. Accepted papers will be published continuously in the journal (as soon as accepted) and will be listed together on the special issue website. Research articles, review articles as well as short communications are invited. For planned papers, a title and short abstract (about 100 words) can be sent to the Editorial Office for announcement on this website.

Submitted manuscripts should not have been published previously, nor be under consideration for publication elsewhere (except conference proceedings papers). All manuscripts are thoroughly refereed through a single-blind peer-review process. A guide for authors and other relevant information for submission of manuscripts is available on the Instructions for Authors page. Entropy is an international peer-reviewed open access monthly journal published by MDPI.

Please visit the Instructions for Authors page before submitting a manuscript. The Article Processing Charge (APC) for publication in this open access journal is 2600 CHF (Swiss Francs). Submitted papers should be well formatted and use good English. Authors may use MDPI's English editing service prior to publication or during author revisions.

Keywords

NP- and #P-complexities
statistical physics
chaos
fractals
phase transition
critical phenomena
Ising model
monomer-dimer model
graph theory
quantum computing
quantum information
boson sampling
cryptography
matrix permanent
stochastic matrix
q-analysis
combinatorics
number-theoretic complexity
randomized approximation scheme
Monte Carlo method
artificial intelligence
machine learning
complex system

Benefits of Publishing in a Special Issue

Ease of navigation: Grouping papers by topic helps scholars navigate broad scope journals more efficiently.
Greater discoverability: Special Issues support the reach and impact of scientific research. Articles in Special Issues are more discoverable and cited more frequently.
Expansion of research network: Special Issues facilitate connections among authors, fostering scientific collaborations.
External promotion: Articles in Special Issues are often promoted through the journal's social media, increasing their visibility.
e-Book format: Special Issues with more than 10 articles can be published as dedicated e-books, ensuring wide and rapid dissemination.

Further information on MDPI's Special Issue polices can be found here.

Published Papers (8 papers)

Download All Papers

Order results

Result details

Show export options Show export options

Select all

Export citation of selected articles as:

Research

24 pages, 3104 KiB

Open AccessArticle

Vector Arithmetic in the Triangular Grid

by Khaled Abuhmaidan, Monther Aldwairi and Benedek Nagy

Entropy 2021, 23(3), 373; https://doi.org/10.3390/e23030373 - 20 Mar 2021

Cited by 2 | Viewed by 3037

Abstract

Vector arithmetic is a base of (coordinate) geometry, physics and various other disciplines. The usual method is based on Cartesian coordinate-system which fits both to continuous plane/space and digital rectangular-grids. The triangular grid is also regular, but it is not a point lattice: it is not closed under vector-addition, which gives a challenge. The points of the triangular grid are represented by zero-sum and one-sum coordinate-triplets keeping the symmetry of the grid and reflecting the orientations of the triangles. This system is expanded to the plane using restrictions like, at least one of the coordinates is an integer and the sum of the three coordinates is in the interval [−1,1]. However, the vector arithmetic is still not straightforward; by purely adding two such vectors the result may not fulfill the above conditions. On the other hand, for various applications of digital grids, e.g., in image processing, cartography and physical simulations, one needs to do vector arithmetic. In this paper, we provide formulae that give the sum, difference and scalar product of vectors of the continuous coordinate system. Our work is essential for applications, e.g., to compute discrete rotations or interpolations of images on the triangular grid. Full article

(This article belongs to the Special Issue Exploring the NP-Complexity of Nature: Critical Phenomena, Chaos, Fractals, Graphs, Boson Sampling, Quantum Computing and More)

► Show Figures

Graphical abstract

43 pages, 8151 KiB

Open AccessArticle

Integrable and Chaotic Systems Associated with Fractal Groups

by Rostislav Grigorchuk and Supun Samarakoon

Entropy 2021, 23(2), 237; https://doi.org/10.3390/e23020237 - 18 Feb 2021

Cited by 5 | Viewed by 2565

Abstract

Fractal groups (also called self-similar groups) is the class of groups discovered by the first author in the 1980s with the purpose of solving some famous problems in mathematics, including the question of raising to von Neumann about non-elementary amenability (in the association with studies around the Banach-Tarski Paradox) and John Milnor’s question on the existence of groups of intermediate growth between polynomial and exponential. Fractal groups arise in various fields of mathematics, including the theory of random walks, holomorphic dynamics, automata theory, operator algebras, etc. They have relations to the theory of chaos, quasi-crystals, fractals, and random Schrödinger operators. One important development is the relation of fractal groups to multi-dimensional dynamics, the theory of joint spectrum of pencil of operators, and the spectral theory of Laplace operator on graphs. This paper gives a quick access to these topics, provides calculation and analysis of multi-dimensional rational maps arising via the Schur complement in some important examples, including the first group of intermediate growth and its overgroup, contains a discussion of the dichotomy “integrable-chaotic” in the considered model, and suggests a possible probabilistic approach to studying the discussed problems. Full article

(This article belongs to the Special Issue Exploring the NP-Complexity of Nature: Critical Phenomena, Chaos, Fractals, Graphs, Boson Sampling, Quantum Computing and More)

► Show Figures

Figure 1

17 pages, 358 KiB

Open AccessArticle

Partial Boolean Functions With Exact Quantum Query Complexity One

by Guoliang Xu and Daowen Qiu

Entropy 2021, 23(2), 189; https://doi.org/10.3390/e23020189 - 3 Feb 2021

Cited by 5 | Viewed by 2065

Abstract

We provide two sufficient and necessary conditions to characterize any n-bit partial Boolean function with exact quantum query complexity 1. Using the first characterization, we present all n-bit partial Boolean functions that depend on n bits and can be computed exactly by a 1-query quantum algorithm. Due to the second characterization, we construct a function F that maps any n-bit partial Boolean function to some integer, and if an n-bit partial Boolean function f depends on k bits and can be computed exactly by a 1-query quantum algorithm, then

F (f)

is non-positive. In addition, we show that the number of all n-bit partial Boolean functions that depend on k bits and can be computed exactly by a 1-query quantum algorithm is not bigger than an upper bound depending on n and k. Most importantly, the upper bound is far less than the number of all n-bit partial Boolean functions for all efficiently big n. Full article

(This article belongs to the Special Issue Exploring the NP-Complexity of Nature: Critical Phenomena, Chaos, Fractals, Graphs, Boson Sampling, Quantum Computing and More)

14 pages, 282 KiB

Open AccessArticle

Elliptic Solutions of Dynamical Lucas Sequences

by Michael J. Schlosser and Meesue Yoo

Entropy 2021, 23(2), 183; https://doi.org/10.3390/e23020183 - 31 Jan 2021

Cited by 3 | Viewed by 1593

Abstract

We study two types of dynamical extensions of Lucas sequences and give elliptic solutions for them. The first type concerns a level-dependent (or discrete time-dependent) version involving commuting variables. We show that a nice solution for this system is given by elliptic numbers. The second type involves a non-commutative version of Lucas sequences which defines the non-commutative (or abstract) Fibonacci polynomials introduced by Johann Cigler. If the non-commuting variables are specialized to be elliptic-commuting variables the abstract Fibonacci polynomials become non-commutative elliptic Fibonacci polynomials. Some properties we derive for these include their explicit expansion in terms of normalized monomials and a non-commutative elliptic Euler–Cassini identity. Full article

(This article belongs to the Special Issue Exploring the NP-Complexity of Nature: Critical Phenomena, Chaos, Fractals, Graphs, Boson Sampling, Quantum Computing and More)

16 pages, 297 KiB

Open AccessArticle

Universal Regimes in Long-Time Asymptotic of Multilevel Quantum System Under Time-Dependent Perturbation

by Vladimir Akulin

Entropy 2021, 23(1), 99; https://doi.org/10.3390/e23010099 - 12 Jan 2021

Viewed by 1780

Abstract

In the framework of an exactly soluble model, one considers a typical problem of the interaction between radiation and matter: the dynamics of population in a multilevel quantum system subject to a time dependent perturbation. The algebraic structure of the model is taken richly enough, such that there exists a strong argument in favor of the fact that the behavior of the system in the asymptotic of long time has a universal character, which is system-independent and governed by the functional property of the time dependence exclusively. Functional properties of the excitation time dependence, resulting in the regimes of resonant excitation, random walks, and dynamic localization, are identified. Moreover, an intermediate regime between the random walks and the localization is identified for the polyharmonic excitation at frequencies given by the Liouville numbers. Full article

(This article belongs to the Special Issue Exploring the NP-Complexity of Nature: Critical Phenomena, Chaos, Fractals, Graphs, Boson Sampling, Quantum Computing and More)

8 pages, 3541 KiB

Open AccessArticle

Random Matrix Theory Analysis of a Temperature-Related Transformation in Statistics of Fano–Feshbach Resonances in Thulium Atoms

by Emil T. Davletov, Vladislav V. Tsyganok, Vladimir A. Khlebnikov, Daniil A. Pershin and Alexey V. Akimov

Entropy 2020, 22(12), 1394; https://doi.org/10.3390/e22121394 - 10 Dec 2020

Cited by 1 | Viewed by 2218

Abstract

Recently, the transformation from random to chaotic behavior in the statistics of Fano–Feshbach resonances was observed in thulium atoms with rising ensemble temperature. We performed random matrix theory simulations of such spectra and analyzed the resulting statistics in an attempt to understand the mechanism of the transformation. Our simulations show that, when evaluated in terms of the Brody parameter, resonance statistics do not change or change insignificantly when higher temperature resonances are appended to the statistics. In the experiments evaluated, temperature was changed simultaneously with optical dipole trap depth. Thus, simulations included the Stark shift based on the known polarizability of the free atoms and assuming their polarizability remains the same in the bound state. Somewhat surprisingly, we found that, while including the Stark shift does lead to minor statistical changes, it does not change the resonance statistics and, therefore, is not responsible for the experimentally observed statistic transformation. This observation suggests that either our assumption regarding the polarizability of Feshbach molecules is poor or that an additional mechanism changes the statistics and leads to more chaotic statistical behavior. Full article

(This article belongs to the Special Issue Exploring the NP-Complexity of Nature: Critical Phenomena, Chaos, Fractals, Graphs, Boson Sampling, Quantum Computing and More)

► Show Figures

Figure 1

12 pages, 1805 KiB

Open AccessArticle

MRI Brain Classification Using the Quantum Entropy LBP and Deep-Learning-Based Features

by Ali M. Hasan, Hamid A. Jalab, Rabha W. Ibrahim, Farid Meziane, Ala’a R. AL-Shamasneh and Suzan J. Obaiys

Entropy 2020, 22(9), 1033; https://doi.org/10.3390/e22091033 - 15 Sep 2020

Cited by 18 | Viewed by 4803

Abstract

Brain tumor detection at early stages can increase the chances of the patient’s recovery after treatment. In the last decade, we have noticed a substantial development in the medical imaging technologies, and they are now becoming an integral part in the diagnosis and treatment processes. In this study, we generalize the concept of entropy difference defined in terms of Marsaglia formula (usually used to describe two different figures, statues, etc.) by using the quantum calculus. Then we employ the result to extend the local binary patterns (LBP) to get the quantum entropy LBP (QELBP). The proposed study consists of two approaches of features extractions of MRI brain scans, namely, the QELBP and the deep learning DL features. The classification of MRI brain scan is improved by exploiting the excellent performance of the QELBP–DL feature extraction of the brain in MRI brain scans. The combining all of the extracted features increase the classification accuracy of long short-term memory network when using it as the brain tumor classifier. The maximum accuracy achieved for classifying a dataset comprising 154 MRI brain scan is 98.80%. The experimental results demonstrate that combining the extracted features improves the performance of MRI brain tumor classification. Full article

(This article belongs to the Special Issue Exploring the NP-Complexity of Nature: Critical Phenomena, Chaos, Fractals, Graphs, Boson Sampling, Quantum Computing and More)

► Show Figures

Figure 1

44 pages, 1786 KiB

Open AccessArticle

Unification of the Nature’s Complexities via a Matrix Permanent—Critical Phenomena, Fractals, Quantum Computing, ♯P-Complexity

by Vitaly Kocharovsky, Vladimir Kocharovsky and Sergey Tarasov

Entropy 2020, 22(3), 322; https://doi.org/10.3390/e22030322 - 12 Mar 2020

Cited by 7 | Viewed by 4049

Abstract

We reveal the analytic relations between a matrix permanent and major nature’s complexities manifested in critical phenomena, fractal structures and chaos, quantum information processes in many-body physics, number-theoretic complexity in mathematics, and ♯P-complete problems in the theory of computational complexity. They follow from a reduction of the Ising model of critical phenomena to the permanent and four integral representations of the permanent based on (i) the fractal Weierstrass-like functions, (ii) polynomials of complex variables, (iii) Laplace integral, and (iv) MacMahon master theorem. Full article

(This article belongs to the Special Issue Exploring the NP-Complexity of Nature: Critical Phenomena, Chaos, Fractals, Graphs, Boson Sampling, Quantum Computing and More)

► Show Figures

Figure 1