Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Applied Optics

Complexity analysis of optical-computing paradigms

Ahmed Louri, Arthur David Post

Published Sep 10, 1992• 11 citations
Publisher

Abstract

Optical computing has been suggested as a means of achieving a high degree of parallelism for both scientific and symbolic applications. While a number of implementations of logic operations have been forwarded, all have some characteristic that prevents their direct extension to functions of a large number of input bits. We analyze several of these implementations and demonstrate that all these implementations require that some measure of the system (area, space-bandwidth product, or time) grow exponentially with the number of inputs. We then suggest an implementation whose complexity is no greater than the best theoretical realization of a Boolean function. We demonstrate the optimality of that realization, to within a constant multiple, for digital optical-computing systems realized by bulk spatially variant elements.

DOI
10.1364/ao.31.005568

Related papers

Complexity of optical computing paradigms: Computational implications and a suggested improvement

Arthur David Post

Optical computing has been suggested as a means of achieving a high degree of parallelism for both scientific and symbolic applications. While a number of implementations of logic operations have been forwarded, all have some characteristic which prevents their direct extension to functions of a large number of input bits. This paper will analyze several of these implementations and demonstrate that all these implementations require some measure of the system (area, space-bandwidth product, or time) to grow exponentially with the number of inputs. We will then suggest an implementation whose complexity is not greater than the best theoretical realization of a boolean function. We will demonstrate the optimality of the realization, to within a constant multiple, for digital optical computing systems realized by bulk space-variant elements.

•Jan 1, 1992•0 citations

Estimating the Number of Junta Variables for Optimizing Boolean Functions in Quantum Memories

Abdulaziz Mutlaq Alotaibi, Samar AbdelAzim, Sattam Alharbi +1 more

Optimizing Boolean function components to have the minimum number of inputs in order to reduce the memory space required during these functions in computing devices is a significant demand. This paper proposes a quantum computation approach based on the degree-of-entanglement quantum computation model to estimate the number of junta variables of an unknown Boolean function presented through an oracle. The time complexity of the developed quantum approach is independent of the number of inputs and depends on an allowable assigned error ϵ. Thus, the time complexity of the developed algorithm is O(ϵ−2), compared to O(2n+1) in the traditional approach. Also, the memory space of the developed approach is linear, O(2n+4), in terms of the number of inputs compared to the exponential memory space O(2n+1) using the traditional approach. Therefore, the developed quantum approach has exponential supremacy in comparison to the traditional approach. The developed approach was implemented practically using both the Qiskit simulator and the IBM real quantum computer. The obtained results expose high statistical fidelities between the empirical and theoretical results.

Mathematics•Oct 25, 2025•0 citations

Model of computation for Fourier optical processors

Thomas J. Naughton

We present a novel and simple theoretical model of computation that captures what we believe are the most important characteristics of an optical Fourier transform processor. We use this abstract model to reason about the computational properties of the physical systems it describes. We define a grammar for our model's instruction language, and use it to write algorithms for well-known filtering and correlation techniques. We also suggest suitable computational complexity measures that could be used to analyze any coherent optical information processing technique, described with the language, for efficiency. Our choice of instruction language allows us to argue that algorithms describable with this model should have optical implementations that do not require a digital electronic computer to act as a master unit. Through simulation of a well known model of computation from computer theory we investigate the general-purpose capabilities of analog optical processors.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•May 24, 2000•25 citations

Foundations of Quantum Circuits

Subhojit Halder

Modern computing has achieved extraordinary scale and speed. Electronic computers emerged commercially in the mid-20th century, and classical computing has since scaled through architectural advances and parallelism. However, many scientifically important problems remain computationally expensive because the underlying state spaces grow exponentially. Quantum computing addresses this challenge by representing and transforming information using quantum-mechanical state vectors and unitary operations. These conventional systems are referred to as classical computers, capable of handling everyday tasks with moderate computational power and speed. Classical computers represent information using bits and process it using deterministic logic operations. While modern classical systems use extensive parallelism (multi-core CPUs, GPUs, and clusters), many important problems still scale poorly because the resources required grow rapidly with input size. Even with significant parallelism, complex problems that involve large combinatorial structures or high-dimensional state spaces often require substantial computational time and resources, motivating the need for more powerful computational paradigms capable of handling such workloads.

Apress eBooks•Jan 1, 2026•0 citations

The Computational Complexity of Linear Optics

Scott Aaronson, Alex Arkhipov

We explain why linear optics is of interest to complexity theory. We show that under plausible conjectures, one cannot classically simulate the outputs of linear optical systems, even approximately. This suggests a gap in computational power between quantum and classical.This talk is based on work done with Scott Aaronson that includes the paper “The Computational Complexity of Linear Optics”[1].

Research in Optical Sciences•Jan 1, 2014•73 citations

Progress in quantum optical computing

H. John Caulfield

Until recently, the paradigm of computing was the Turing machine and its numerous equivalents. All operations are made with state machines. Each operation is irreversible and brings about an increase of entropy and, therefore, an expenditure of energy of at least kTln2 per bit. We show that optics allows the first practical quantum mechanical digital processors. These processors require digital input and produce digital output but need no intermediate state machines. We show that, in the sense of not requiring material devices which would otherwise be required, nothing is superior to something for computing.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Apr 24, 1992•0 citations
Optical computing has been suggested as a means of achieving a high degree of parallelism for both scientific and symbolic applications. While a number of implementations of logic operations have been forwarded, all have some characteristic that prevents their direct extension to functions of a large number of input bits. We analyze several of these implementations and demonstrate that all these implementations require that some measure of the system (area, space-bandwidth product, or time) grow exponentially with the number of inputs. We then suggest an implementation whose complexity is no greater than the best theoretical realization of a Boolean function. We demonstrate the optimality of that realization, to within a constant multiple, for digital optical-computing systems realized by bulk spatially variant elements.
Optical computing has been suggested as a means of achieving a high degree of parallelism for both scientific and symbolic applications. While a number of implementations of logic operations have been forwarded, all have some characteristic which prevents their direct extension to functions of a large number of input bits. This paper will analyze several of these implementations and demonstrate that all these implementations require some measure of the system (area, space-bandwidth product, or time) to grow exponentially with the number of inputs. We will then suggest an implementation whose complexity is not greater than the best theoretical realization of a boolean function. We will demonstrate the optimality of the realization, to within a constant multiple, for digital optical computing systems realized by bulk space-variant elements.
Optimizing Boolean function components to have the minimum number of inputs in order to reduce the memory space required during these functions in computing devices is a significant demand. This paper proposes a quantum computation approach based on the degree-of-entanglement quantum computation model to estimate the number of junta variables of an unknown Boolean function presented through an oracle. The time complexity of the developed quantum approach is independent of the number of inputs and depends on an allowable assigned error ϵ. Thus, the time complexity of the developed algorithm is O(ϵ−2), compared to O(2n+1) in the traditional approach. Also, the memory space of the developed approach is linear, O(2n+4), in terms of the number of inputs compared to the exponential memory space O(2n+1) using the traditional approach. Therefore, the developed quantum approach has exponential supremacy in comparison to the traditional approach. The developed approach was implemented practically using both the Qiskit simulator and the IBM real quantum computer. The obtained results expose high statistical fidelities between the empirical and theoretical results.
We present a novel and simple theoretical model of computation that captures what we believe are the most important characteristics of an optical Fourier transform processor. We use this abstract model to reason about the computational properties of the physical systems it describes. We define a grammar for our model's instruction language, and use it to write algorithms for well-known filtering and correlation techniques. We also suggest suitable computational complexity measures that could be used to analyze any coherent optical information processing technique, described with the language, for efficiency. Our choice of instruction language allows us to argue that algorithms describable with this model should have optical implementations that do not require a digital electronic computer to act as a master unit. Through simulation of a well known model of computation from computer theory we investigate the general-purpose capabilities of analog optical processors.
Modern computing has achieved extraordinary scale and speed. Electronic computers emerged commercially in the mid-20th century, and classical computing has since scaled through architectural advances and parallelism. However, many scientifically important problems remain computationally expensive because the underlying state spaces grow exponentially. Quantum computing addresses this challenge by representing and transforming information using quantum-mechanical state vectors and unitary operations. These conventional systems are referred to as classical computers, capable of handling everyday tasks with moderate computational power and speed. Classical computers represent information using bits and process it using deterministic logic operations. While modern classical systems use extensive parallelism (multi-core CPUs, GPUs, and clusters), many important problems still scale poorly because the resources required grow rapidly with input size. Even with significant parallelism, complex problems that involve large combinatorial structures or high-dimensional state spaces often require substantial computational time and resources, motivating the need for more powerful computational paradigms capable of handling such workloads.
Until recently, the paradigm of computing was the Turing machine and its numerous equivalents. All operations are made with state machines. Each operation is irreversible and brings about an increase of entropy and, therefore, an expenditure of energy of at least kTln2 per bit. We show that optics allows the first practical quantum mechanical digital processors. These processors require digital input and produce digital output but need no intermediate state machines. We show that, in the sense of not requiring material devices which would otherwise be required, nothing is superior to something for computing.