The complexity of quantum computation

Hossein Naderi, Alireza Shojaei, Saeed Rokooei

The ever-growing complexity of construction projects on the one hand, and the increasing use of emerging technologies in the AEC industry on the other hand, have significantly escalated computational complexity. This trend is expected to continue. However, conventional computing tools and technologies highly rely on classical computing techniques that may not be able to handle computational tasks which become larger and more complex over time. Quantum computing (QC) is a fast-evolving technology that promises to completely revolutionize the computation capabilities in various fields, including engineering, by enabling complex computations that currently are impossible or prohibitively time consuming. As a result, QC can be seen as a next-generation solution to address computational challenges arising in the AEC’s today and future. However, scant attention has been drawn to what the QC can bring to the AEC industry. This study reviews the existing QC literature to explore AEC applications that could benefit from QC-based methods, and the potential challenges associated with their implementation in the AEC industry. Illustrating a clear outlook of the potential advantages and challenges, the study also helps to set realistic expectations over the potential improvement that QC can offer over conventional techniques.

John Watrous

Hossein Naderi, Alireza Shojaei, Saeed Rokooei

The ever-growing complexity of construction projects on the one hand, and the increasing use of emerging technologies in the AEC industry on the other hand, have significantly escalated computational complexity. This trend is expected to continue. However, conventional computing tools and technologies highly rely on classical computing techniques that may not be able to handle computational tasks which become larger and more complex over time. Quantum computing (QC) is a fast-evolving technology that promises to completely revolutionize the computation capabilities in various fields, including engineering, by enabling complex computations that currently are impossible or prohibitively time consuming. As a result, QC can be seen as a next-generation solution to address computational challenges arising in the AEC’s today and future. However, scant attention has been drawn to what the QC can bring to the AEC industry. This study reviews the existing QC literature to explore AEC applications that could benefit from QC-based methods, and the potential challenges associated with their implementation in the AEC industry. Illustrating a clear outlook of the potential advantages and challenges, the study also helps to set realistic expectations over the potential improvement that QC can offer over conventional techniques.

Marco O. Lanzagorta, Jeffrey K. Uhlmann

Lance Fortnow, John D. Rogers

P. Heszler, László B. Kish

A model of parallel optical computer for Fourier transform tasks is built. The computer operates in both quantum and classical modes. The quantum computer (QC) works with entangled photons and the input gates are n-qubit sensitive, while the classical computer (CC) operates without entanglement. The information capacity (I) for both CC and QC is given as a function of number of qubits and Np (number of photons per input pixel). It is shown that the information capacity significantly increases for the quantum computer compared to the classical one as the number of qubits is increased, assuming that Np is constant for both the QC and CC, i.e. same amount of energy input is assumed for the computers. However, it is also pointed out that the complexity of the QC significantly increases, too. To quantify this, we introduce a new physical quantity called physical complexity (noted as Q). We define the physical complexity (Q) of a computer as ∑i,klog2nkai where k runs over all the gates/elements in the computer; nai is the number of distinguishable states what a gate can set for ai. For QC ai is defined as the ith coefficient of the wave function. For CC it is the ith independent component of the Fourier transform of the energy flow what a particular gate is able to control. By using this definition we show that, for both the quantum and classical computers built in this work, I ≤ Q, in other words the information capacity is less or equal than the physical complexity. Intuitively we suggest that this is a general law that is valid for every computer irrespectively of type, quantum or classic, and architecture.