An Enhanced Photonic Quantum Finite Automaton

Abstract

In a recent paper we have described an optical implementation of a measure-once one-way quantum finite automaton recognizing a well-known family of unary periodic languages, accepting words not in the language with a given error probability. To process input words, the automaton exploits the degree of polarization of single photons and, to reduce the acceptance error probability, a technique of confidence amplification using the photon counts is implemented. In this paper, we show that the performance of this automaton may be further improved by using strategies that suitably consider both the orthogonal output polarizations of the photon. In our analysis, we also take into account how detector dark counts may affect the performance of the automaton.

1. Introduction

In the recent years, quantum computers have eventually leaped out of the laboratories [1] and become accessible to a still growing community interested in investigating their actual potentialities. Nevertheless, a full-featured quantum computer is still far from being built. However, it is reasonable to think of classical computers exploiting some quantum components. In this framework, quantum finite automata [2,3]—theoretical models for quantum machines with finite memory—may play a key role, as they model small-size quantum computational devices that can be embedded in classical ones. Among possible models, the so-called measure-once one-way quantum finite automaton [4,5] is the simplest, and it has been shown to be the most promising for a physical realization [6]. In fact, restricted models of computation, such as quantum versions of finite automata, have been theoretically studied [7,8,9] and, very recently, experimentally investigated [6,10].

In [6], a measure-once one-way quantum finite automaton recognizing a well-known family of unary periodic languages [4], namely, languages $L_m$, has been implemented using quantum optical technology [11,12]. In our implementation, a given input word is accepted by the automaton, with a given error probability, whenever a single photon arrives at the output of the device with a specific polarization. In particular, the experimental realization, based on the manipulation of single-photon polarization and photodetection, has demonstrated the possibility of building small quantum computational component to be embedded in more sophisticated and precise quantum finite automata or also in other computational systems and approaches [13,14,15]. Albeit the photonic automaton realized in [6] is fed with single photons, it works in a regime where polarized laser pulses (coherent states) are enough, up to detecting the intensity of the output signals instead of counting the number of photons successfully passing through the device with a given polarization (see in [6] for details).

In this paper, we propose an enhanced version of our photonic automaton mentioned above, where, to further reduce the acceptance error probability, we consider not only the photons with the “correct” polarization, but also the other ones. To achieve this goal, the use of single-photon techniques turns out to be crucial, such as the detection of coincidence count to reduce the dark-count rate of the photodetectors [16]. Analytical and numerical results, supported by simulated experiments, show that the enhanced version allows to reduce the error probability by orders of magnitude compared to the previous version, or, analogously, to drastically reduce the mean number of photons needed to achieve the same performance.

The paper is structured as follows. As our work requires some previous knowledge from Theoretical Computer Science about formal languages and finite automata, Section 2 is devoted to introduce the reader to these topics, providing the relevant motivations. In Section 3, we briefly review basics of formal language theory and the definition of a measure-once one-way quantum finite automaton. Section 4 describes the implementation of the measure-once one-way quantum finite automaton based on the polarization of single photons, linear optical elements, and photodetectors. In Section 5, we explain how to improve the confidence of the obtained measure-once one-way quantum finite automaton by processing the number of counts at the detectors. We also introduce new strategies that reduce the error probability, namely, the probability that a “wrong” word is accepted by the automaton or a “correct” word is rejected. The numerical results and the simulated experiments are reported in Section 6. We close the paper with some concluding remarks in Section 7.

2. Formal Languages, Finite Automata, and Quantum Computing

In this section, we would like to expand on motivations that have been driving our research covered by the present contribution and the previous one in [6]. The aim of our work, that bridges between Theoretical Computer Science and Experimental Quantum Optics, has been and is to show that a quantum computing device with finite memory is physically realizable by means of photonics, using a very limited amount of “quantum hardware”. To the best of our knowledge, our physical implementation, described here and in [6], of a quantum finite automaton for language acceptation is the first proposed in the literature. Thus, we have shown how the quantum behaviour of microscopic systems can actually represent a computational resource, as theoretically established within the discipline of Quantum Computing. From this perspective, the simple language $L_m$, introduced in the next section and for which we build our photonic quantum finite automaton, is not really the point here. Instead, the point is the concrete creation of a programmable fully quantum computer with finite memory.

With this being said, we would also like to quickly comment on the language $L_m$ from a Theoretical Computer Science viewpoint. Notwithstanding its simplicity, the language $L_m$ plays a crucial role in Descriptional Complexity Theory (see, e.g., in [17,18,19,20,21]), the area of Formal Language Theory in which the size of computational models is investigated. In particular, a well-consolidated trend in Descriptional Complexity is devoted to study the size of several types of finite automata. The reader is referred to, e.g., the work in [22] for extensive presentations of automata theory. Very roughly speaking, the hardware of a (one-way) finite automaton A features a read-only input tape consisting of a sequence of cells, each one being able to store an input symbol. The tape is scanned by an input head always moving one position right at each step. At each time during the computation of A, a finite state control is in a state from a finite set Q. Some of the states in Q are designated as accepting states, while a state $q_0\in Q$ is a designated initial state. The computation of A on a word (i.e., a finite sequence of symbols) $\omega$ from a given input alphabet begins by having (i) $\omega$ stored symbol by symbol, left to right, in the cells of the input tape; (ii) the input head scanning the leftmost tape cell; and (iii) the finite state control being in the state $q_0$. In a move, A reads the symbol below the input head and, depending on such a symbol and the state of the finite state control, it switches to the next state according to a fixed transition function and moves the input head one position forward. We say that A accepts $\omega$ whenever it enters an accepting state after scanning the rightmost symbol of $\omega$; otherwise, A rejects $\omega$. The language accepted by A consists of all the input words accepted by A.

The one described so far is the original model of a finite automaton, called deterministic. Several variants of such an original model have been introduced and studied in the literature, sharing the same hardware but different dynamics. Therefore, we have nondeterministic, probabilistic and, recently, quantum finite automata (see, e.g., in [23,24,25]). Furthermore, two-way automata are studied, where the input head can move back and forth on the input tape.

Finite automata represent a formidable theoretical model used in the design and analysis of several devices such as the control units for vending machines, elevators, traffic lights, combination locks, etc. Particularly important is the use of finite automata in very large-scale integration (VLSI) design, namely, in the project of sequential networks which are the building blocks of modern computers and digital systems. Very roughly speaking, a sequential network is a boolean circuit equipped with memory. Engineering a sequential network typically requires modeling its behaviour with a finite automaton whose number of states directly influences the amount of hardware (i.e., the number of logic gates) employed in the electronic realization of the sequential network. From this point of view, having fewer states in the modeling finite automaton directly results in employing smaller hardware which, in turn, means having less energy absorption and fewer cooling problems. These “physical” considerations, that are of paramount importance given the current level of digital device miniaturization, have led to define the size of a finite automaton as the number of its states. In particular, reducing or increasing the number of states is studied, when using different computational paradigms (e.g., deterministic, nondeterministic, probabilistic, quantum, one-way, and two-way) on a finite automaton to perform a given task. Here, is where our simple language $L_m$ comes into play. In fact, this language is universally used as a benchmark to emphasize the succinctness of several types of automata. Several results in the literature shows that accepting $L_m$ on classical models of finite state automata is particularly size-consuming (i.e., it requires a great number of states), while only two basis states are enough on quantum finite automata, as we will see in the next section.

Modular design frameworks have been theoretically proposed [7,8,9], where more reliable and sophisticated quantum automata can be built by suitably composing (see, e.g., in [26]) easy-to-obtain variants of the quantum automaton for $L_m$. Hence, our work provides crucial and concrete quantum components for such frameworks, and suggest investigating a physical implementation of some automata composition laws. More generally, the Krohn–Rhodes decomposition theorem [27] states that any classical finite automaton can be simulated by composing very “simple” finite automata: one of these simple automata is exactly the one for $L_m$. From this perspective, our photonic quantum automaton could be hardwired into “hybrid” architectures joining classical and quantum components to build very succinct finite state devices operating in environments where dimension and energy absorption are particularly critical issues (e.g., drone or robot-based systems [28]).

3. Measure-Once One-Way Quantum Finite Automaton

Here, we briefly overview the main concepts on automata and formal language theory. We refer the interested reader to any of the standard books on these subjects (see, e.g., in [22]), as well as to our contribution [6].

An alphabet is any finite set $\Sigma$ of elements called symbols. A word on $\Sigma$ is any sequence ${\sigma }_1{\sigma }_2\cdots {\sigma }_n$ with ${\sigma }_i\in \Sigma$. The set of all words on $\Sigma$ is denoted by ${\Sigma }^{\ast }$. A language L on $\Sigma$ is any subset of ${\Sigma }^{\ast }$, i.e., $L\subseteq {\Sigma }^{\ast }$. If $|\Sigma |=1$, we say that $\Sigma$ is a unary alphabet, and languages on unary alphabets are called unary languages. In case of unary alphabets, we customarily let $\Sigma =\left\{a\right\}$ so that a unary language is any set $L\subseteq a^{\ast }$. We let $a^k$ be the unary word obtained by concatenating k times the symbol a.

In what follows, we will be interested in the unary language $L_m$ defined as

$$L_m=\{a^k\mid k\in \mathbb{N}andk\left(\mathrm{mod}m\right)=0\}.$$

(1)

This language is rather famous in the realm of automata theory, since it has proven particularly “size-consuming” to be accepted by several models of classical automata, as the number of needed states increases with m [6]. The reader may find a deep investigation on this fact in the literature [22,29,30,31]. On the other hand, as presented in [6], very succinct measure-once one-way quantum finite automata (1qfa’s, from now on) may be designed and physically realized for $L_m$. Let us now sketch the main ingredients for a 1qfa accepting $L_m$.

If we consider the two orthogonal states $|H\rangle =(1,0)$ and $|V\rangle =(0,1)$, the 1qfa is defined as (here we use the formalism based on the Dirac’s notation; the analysis based on a more general formalism can be found in [6])

$${\mathcal{A}}_1=\left\{|H\rangle ,U_m,P^H\right\}$$

(2)

where $|H\rangle$ represents the initial state, the unitary operation applied by the automaton upon processing any input symbol a is defined as

$$\begin{array}{}\hfill \left(3\right)& U_m=exp(-i{\theta }_m{\sigma }_y)\hfill \hfill \left(4\right)& =\left(\begin{array}{cc}cos{\theta }_m& sin{\theta }_m\\ -sin{\theta }_m& cos{\theta }_m\end{array}\right).\hfill \end{array}$$

with ${\theta }_m=\pi /m$ and ${\sigma }_y$ the Pauli matrix, while $P^H=|H\rangle \langle H|$ is the projector onto the mono-dimensional accepting subspace spanned by $|H\rangle$. The probability $p_{{\mathcal{A}}_1}\left(a^k\right)$ that the 1qfa ${\mathcal{A}}_1$ accepts the word $a^k$ writes as

$$\begin{array}{}\hfill \left(5\right)& p_{{\mathcal{A}}_1}\left(a^k\right)=p^H\left(a^k\right)\equiv |\langle H|U_m^k{|H\rangle |}^2\hfill \hfill \left(6\right)& \hspace{1em}\hspace{1em} ={cos}^2\left(k{\theta }_m\right)\to \left\{\begin{array}{cc}=1\hfill & k\left(\mathrm{mod}m\right)=0\hfill \\ \le {cos}^2{\theta }_m\hfill & \mathrm{otherwise}.\hfill \end{array}\right.\hfill \end{array}$$

Therefore, the 1qfa ${\mathcal{A}}_1$ perfectly recognizes the word $a^k\in L_m$, as we can set a cut point $\lambda$ and an isolation $\rho$ to the following values (see in [6] for details on accepting languages with isolated cut point)

$$\lambda =\frac{1+{cos}^2{\theta }_m}{2}\mathrm{and}\rho =\frac{1-{cos}^2{\theta }_m}{2}.$$

(7)

However, ${\mathcal{A}}_1$ may also recognize an input word not in $L_m$ with a non-null probability. In the following, we let $a^{k_1}$ with $k_1\left(modm\right)=1$ any of the word with the highest probability of erroneously being accepted, i.e., ${cos}^2{\theta }_m$, which tends to 1 as m gets large. This can be seen also by the fact that $\rho \to 0$ as m increases.

As matter of fact, we can also introduce the following 1qft, where we still consider the initial state $|H\rangle$, but, at the output, we focus on the final projection involving the state $|V\rangle$, namely

$${\mathcal{A}}_2=\left\{|H\rangle ,U_m,\mathbb{I}-P^V\right\},$$

(8)

where $P^V=|V\rangle \langle V|$. Indeed, ${\mathcal{A}}_2$ is formally equivalent to ${\mathcal{A}}_1$, as $\mathbb{I}-P^V\equiv P^H$. In fact, the probability of accepting a word is now given by

$$p_{{\mathcal{A}}_2}\left(a^k\right)=1-p^V\left(a^k\right)\to \left\{\begin{array}{cc}=1\hfill & k\left(\mathrm{mod}m\right)=0\hfill \\ \le {cos}^2{\theta }_m\hfill & \mathrm{otherwise}\hfill \end{array}\right.$$

(9)

that is the same as in Equation (6), as one may expect. Nevertheless, we show in the next section that the two are not equivalent in a photonic implementation for reasons that will be clear soon.

4. Photonic Implementation of the 1qfa

A photonic implementation of the 1qfa described in the previous section was proposed and demonstrated in [6]. Figure 1 depicts the main elements of the enhanced version of the automata we will describe in the following.

The state of the automaton is encoded in the polarization of single photons, and the Hilbert space is $\mathcal{H}=\mathrm{span}\left\{\right|H\rangle ,|V\rangle \}$. A single photon source generates a horizontal-polarized state, $|H\rangle$, which is sent to k rotators of polarization, $a^k$ being the input word to be processed. Each rotator corresponds to a unitary rotation of an amount ${\theta }_m$, which is thus language-dependent. After the rotators, the single photon state reads

$$|k{\theta }_m\rangle =cos\left(k{\theta }_m\right)|H\rangle +sin\left(k{\theta }_m\right)|V\rangle$$

(10)

and it is sent to a polarizing beam splitter (PBS; see Figure 1) that reflects the vertical polarization component and transmits the horizontal one. Finally, two photodetectors placed after the PBS realize the projective measure of $P^H$ and $P^V$. As the reader can see, the scheme is almost the same of that proposed in [6], but here we will implement a new inference strategy exploiting the outcomes from both the detectors.

As we observed in the previous section, the automata ${\mathcal{A}}_1$ and ${\mathcal{A}}_2$ accept with certainty a word $a^k$ that belongs to $L_m$. However, there is a high probability that an incorrect word, such as $a^{k_1}$ with $k_{1}modm\ne 0$ can be accepted, as we can see from Equations (6) and (9). Therefore, strategies based on a single-photon shot may not be the optimal way to recognize an arbitrary word $a^k$.

5. Confidence Amplification: An Enhanced Strategy

To reduce the probability of error, we can adopt a technique of confidence amplification as also proposed in [6], namely, we sent a mean number of photons $\langle N_{\mathrm{c}}\rangle$ and we count the number of click $N_{\mathrm{c}}^x\left(k\right)$ at the photodetector $x=H,V$, see Figure 1. Therefore, the observed detection frequency at detector $x=H,V$ for an input word $a^k$ will be

$$f_k^x=\frac{N_{\mathrm{c}}^x\left(k\right)}{\langle N_{\mathrm{c}}\rangle }\stackrel{\langle N_{\mathrm{c}}\rangle \gg 1}{\to }{p}_{{\mathcal{A}}_{i=1,2}}^x\left(a^k\right).$$

(11)

Thereafter, we turn our problem into that of discriminating among the corresponding detection frequencies and, in particular, we can focus on those related to $k=0$ (or, equivalently, $kmodm=0$) and $k=1$ (or, more in general, $kmodm=1$), since if $k>1$ one has $f_k^H<f_1^H$ ($f_k^V>f_1^V$). To implement this strategy, we set a threshold frequency as

$$f_{\mathrm{th}}^x=\frac{f_0^x+f_1^x}{2}=\left\{\begin{array}{cc}{\displaystyle \frac{1+f_1^H}{2}}\hfill & x=H,\hfill \\ {\displaystyle \frac{f_1^V}{2}}\hfill & x=V,\hfill \end{array}\right.$$

(12)

where $f_1^H$ ($f_1^V$) is the highest (lowest) frequency of erroneously accepted words $a^{k_1}$, while $f_0^H$ ($f_0^V$) is the frequency corresponding to the correct word. In this formula, we have distinguished the two different strategies: for the H detector, $f_0^H=1$, as the corresponding photon will always be detected; instead, for the V detector, $f_0^V=0$, as no photon is detected when the word belongs to $L_m$. Therefore, the strategy is to accept the word if $f_k^H>f_{\mathrm{th}}^H$ ($f_k^V<f_{\mathrm{th}}^V$) and reject it if $f_k^H<f_{\mathrm{th}}^H$ ($f_k^V>f_{\mathrm{th}}^V$). From now on, we will refer to these strategies as “H strategy” and “V strategy”, respectively.

In an ideal scenario, namely, without fluctuations in the sent number of photons, it is clear that the two approaches are complementary and yield to the same conclusion, as the single detections in H and V are perfectly correlated. Moreover, given that only the words $a^k\in L_m$ satisfy the condition $f_k>f_{\mathrm{th}}$, with this strategy we have a zero error probability, provided that $\langle N_{\mathrm{c}}\rangle$ is large enough such that the integer part of $N_{\mathrm{th}}^H$ ($N_{\mathrm{th}}^V$) is strictly positive (negative) than $N_{\mathrm{c}}^H\left(k_1\right)$ ($N_{\mathrm{c}}^V\left(k_1\right)$), i.e., we have the conditions

$$\begin{array}{}\hfill \left(13\right)& \lfloor N_{\mathrm{th}}^H\rfloor =\lfloor \frac{\langle N_{\mathrm{c}}\rangle (1+{cos}^2{\theta }_m)}{2}\rfloor >\lfloor \langle N_{\mathrm{c}}\rangle {cos}^2{\theta }_m\rfloor ,\hfill \hfill \left(14\right)& \lfloor N_{\mathrm{th}}^V\rfloor =\lfloor \frac{\langle N_{\mathrm{c}}\rangle {sin}^2{\theta }_m}{2}\rfloor <\lfloor \langle N_{\mathrm{c}}\rangle {sin}^2{\theta }_m\rfloor .\hfill \end{array}$$

In Figure 2 (black lines and dots), we report the minimum values of $\langle N_c\rangle$ such that the last two inequalities hold.

In a realistic scenario, the photo-detection is influenced by two distinct noisy effects that can affect the error probability. The first is that the number of detected photons follows a Poisson distribution [32], that is, we have

$$\mathrm{Poi}(n;\mu )=\frac{{\mu }^n{e}^{-\mu }}{n!}$$

(15)

that is, the probability of detect n photons depends on the average number of detected photons $\mu$. How this affects the error probability has been thoroughly addressed both theoretically and experimentally in [6].

The second effect that we should consider in order to apply our enhanced strategy is due to the dark counts, namely, the random counts registered by the detector without any incident light on it. Being still related to the detection process, also the dark counts follow a Poissonian distribution, whose mean $\langle N_{\mathrm{dc}}\rangle$ depends on the particular detector one choose to use. In a typical quantum optics experiment, the dark-count rate ranges from tens to hundreds of photons per second, but this number can be drastically reduced by using coincidence counting techniques [16], up to making this effect negligible. For instance, in the implementation in [6] the dark counts where only 0.001% of the effective coincidence counts. As the dark counts occurs randomly, we cannot distinguish between a dark count and signal one. Therefore, the probability of detecting N photon in the H or V photodetector for a word $a^k$ is finally given by

$$\begin{array}{}\hfill \left(16\right)& P_k^x\left(N\right)=\sum _{n=0}^{+\infty }\sum _{m=0}^{+\infty }\mathrm{Poi}\left(n;{\eta }^x\right)\mathrm{Poi}\left(m;\langle N_{\mathrm{dc}}\rangle \right){\delta }_{n+m,N}\hfill \hfill \left(17\right)& \hspace{1em}\hspace{1em}=\mathrm{Poi}(N;{\mu }_k^x)\hfill \end{array}$$

where ${\eta }^H=\langle N_{\mathrm{c}}\rangle {cos}^2\left(k{\theta }_m\right)$ and ${\eta }^V=\langle N_{\mathrm{c}}\rangle {sin}^2\left(k{\theta }_m\right)$, while we have defined the overall mean number of detected photons as

$$\begin{array}{c}\hfill {\mu }_k^H=\langle N_{\mathrm{c}}\rangle {cos}^2\left(k{\theta }_m\right)+\langle N_{\mathrm{dc}}\rangle \mathrm{and}{\mu }_k^V=\langle N_{\mathrm{c}}\rangle {sin}^2\left(k{\theta }_m\right)+\langle N_{\mathrm{dc}}\rangle .\end{array}$$

(18)

As we noticed above, the dark count rate is usually very small with respect to the detected count rate of the signal. Therefore, for the H detector which detects the higher number of photons, see Equation (18), they are relevant only when $\langle N_{\mathrm{c}}\rangle \sim \langle N_{\mathrm{dc}}\rangle$. On the contrary, for the V detector, detecting the lower number of photons, their role is fundamental in determining the performance of the photonic automaton, as ${\mu }_m^V={\mu }_{\mathrm{dc}}=\langle N_{\mathrm{dc}}\rangle$. This is the main difference between the two strategies: in the first, we need to distinguish between two finite mean numbers of photon ${\mu }_m^H=\langle N_{\mathrm{c}}\rangle +\langle N_{\mathrm{dc}}\rangle$ and ${\mu }_{k_1}^H$, while in the second case, we need to distinguish between the noise due to dark counts, being ${\mu }_m^V=\langle N_{\mathrm{dc}}\rangle$, and ${\mu }_{k_1}^V$. However, to assess the performance of second strategy with respect the first one, we need to evaluate the probability of errors in the two cases.

Let us first find the threshold values in the two different strategy. We need to find the intersection between two Poissonian distributions for a word belong to $L_m$ and a word $a^{k_1}$ with highest probability of being erroneously being accepted, as show in Figure 3. By imposing $\mathrm{Poi}(N_{\mathrm{th}}^x;{\mu }_1^x)=\mathrm{Poi}(N_{\mathrm{th}}^x;{\mu }_m^x)$, where $x=H,V$, we find an exact solution for $N_{\mathrm{th}}^x$ given by (see the vertical dashed line in Figure 3)

$$N_{\mathrm{th}}^x=\frac{{\mu }_m^x-{\mu }_{k_1}^x}{ln{\mu }_m^x-ln{\mu }_{k_1}^x}.$$

(19)

To highlight the dark counts effects, we introduce the ratio $\eta =\langle N_{\mathrm{dc}}\rangle /\langle N_{\mathrm{c}}\rangle$, and we have

$$\begin{array}{}\hfill \left(20\right)& N_{\mathrm{th}}^H=\frac{\langle N_{\mathrm{c}}\rangle {sin}^2{\theta }_m}{ln\left(1+\eta \right)-ln\left({cos}^2{\theta }_m+\eta \right)}\prime \hfill \hfill \left(21\right)& N_{\mathrm{th}}^V=\frac{\langle N_{\mathrm{c}}\rangle {sin}^2{\theta }_m}{ln\left({sin}^2{\theta }_m+\eta \right)-ln\left(\eta \right)}.\hfill \end{array}$$

In our framework, the accepting problem is introduced as binary discrimination between the correct word and the word with the highest probability of error. However, in the photonic realization of the automata [6], when the number of input photons is small and m is large, also word with larger $k\left(\mathrm{mod}m\right)$ may contribute to the error. For this reason, like in the ideal case, we establish the minimum number of input photon ${\langle N_{\mathrm{c}}\rangle }^{min}$ which are necessary to faithfully consider the problem as binary discrimination.

To have faithfully binary discrimination the fluctuations due to the word with the second-largest probability of error, i.e., a word $a^{k_2}$ with $k_2\left(\mathrm{mod}m\right)=2$, must be much larger than the fluctuations due to the correct word, where here for “large” we mean at least two standard deviations. In this way, the discrimination can be considered only between the words $a^m$ and $a^{k_1}$. In the case of a Poissonian random variable, the standard deviation is the square root of the mean for Poissonian random variables. Hence, we have the two conditions, respectively, for the H and V detector

$$\begin{array}{c}\hfill {\mu }_{k_2}^H+2\sqrt{{\mu }_{k_2}^H}<{\mu }_m^H-2\sqrt{{\mu }_m^H},\end{array}$$

(22)

$$\begin{array}{c}\hfill {\mu }_{Dc}+2\sqrt{{\mu }_{Dc}}<{\mu }_{k_2}^V-2\sqrt{{\mu }_{k_2}^V}.\end{array}$$

(23)

In the first one we ask that the fluctuations due to the word with the second largest probability of error, i.e., a word $k_2$ with $k_2\left(\mathrm{mod}m\right)=2$ are much larger than the fluctuations due to dark counts. In a similar way, we define the threshold for the horizontal detector. These equations can be solved for $\langle N_{\mathrm{c}}\rangle$ and set a lower bounds for it such that the probability of error can be evaluated in term of a binary discrimination problem, as shown in Figure 2 (red and blue lines and points).

Now, we can evaluate the probability of error for the two strategies. Indeed, this is equal to

$$p_e^x=p\left(a^{k_1}\right)p^x(a^{k_1}\to a^m)+p\left(a^m\right)p^x(a^m\to a^{k_1}),$$

(24)

where we have denoted $p^x(a^i\to a^j)$ as the probability of detecting the word $a^i$ as $a^j$ by the detector $x=H,V$. As we have no a priori knowledge on the input word we set the prior probabilities $p\left(a^{k_1}\right)=p\left(a^m\right)=1/2$, and for the V detector we obtain

$$\begin{array}{}\hfill \left(25\right)& P_e^V=\frac{1}{2}\left[\sum _{n=0}^{\lfloor N_{\mathrm{th}}^V\rfloor }\frac{{\left({\mu }_{k_1}^V\right)}^n{e}^{-{\mu }_{k_1}^V}}{n!}+\sum _{n=\lfloor N_{\mathrm{th}}^V\rfloor +1}^{+\infty }\frac{{\mu }_{\mathrm{dc}}^n{e}^{-{\mu }_{\mathrm{dc}}}}{n!}\right]\hfill \hfill \left(26\right)& =\frac{1}{2}\left[1-\frac{\Gamma (\lfloor N_{\mathrm{th}}^V\rfloor +1,{\mu }_{\mathrm{dc}})-\Gamma (\lfloor N_{\mathrm{th}}^V\rfloor +1,{\mu }_{k_1}^V)}{\lfloor N_{\mathrm{th}}^V\rfloor !}\right]\hfill \hfill \left(27\right)& =\frac{1}{2}\left[1-{\int }_{N_{\mathrm{dc}}}^{N_{\mathrm{c}}{sin}^2{\theta }_m+N_{\mathrm{dc}}}\frac{e^{-t}{t}^{\lfloor N_{\mathrm{th}}^V\rfloor }}{\lfloor N_{\mathrm{th}}^V\rfloor !}dt\right],\hfill \end{array}$$

where $\Gamma (a,x)$ is the incomplete Gamma function

$$\Gamma (a,x)={\int }_x^{+\infty }{e}^{-t}{t}^{a-1}dt.$$

(28)

Analogously, we may evaluate the probability of error for the detection of a horizontally polarized photon, i.e.,

$$\begin{array}{cc}\hfill P_e^H& =\frac{1}{2}\left[\sum _{n=0}^{\lfloor N_{\mathrm{th}}^H\rfloor }\frac{{\left({\mu }_m^H\right)}^n{e}^{-{\mu }_m^H}}{n!}+\sum _{n=\lfloor N_{\mathrm{th}}^H\rfloor +1}^{+\infty }\frac{{\left({\mu }_{k_1}^H\right)}^n{e}^{-{\mu }_{k_1}^H}}{n!}\right].\hfill \end{array}$$

(29)

Eventually, we can introduce a third strategy that combines the two described so far: for each beam of photon, we propose to measure both the H and V polarization and to combine the results so obtained. From a theoretical point of view, this is equivalent to the automata presented before, as in the ideal case the two detectors perfectly agree, i.e., one sees the photon and the other one does not see it. However, in the non-ideal case, noisy fluctuations affect photodetection. As the fluctuations in the H detector are independent from the one in the V detector, the probability of erroneously accepting it by looking at both H and V is given as

$$p_e^J=p\left(a^{k_1}\right)p^H(a^{k_1}\to a^m)p^V(a^{k_1}\to a^m)+p\left(a^m\right)p^H(a^m\to a^{k_1})p^V(a^m\to a^{k_1})$$

(30)

where J here stands for joint.

6. Numerical Results and Simulations

The comparison of the three strategies is reported in Figure 4. We see that the V strategy outperforms the H strategy for all the possible values of input photon, reaching almost a negligible error for approximately an order of magnitude less than the H strategy. The joint strategy realizes a further enhancement, even though the $p_e^J$ approaches 0 with the same order of magnitude of $\langle N_{\mathrm{c}}\rangle$ as $p_e^V$. We have also reported the solution for the inequalities (22) and (23) as a point along the corresponding line: for smaller value, the probabilities of error are not reliable as the contribution of the words with larger $k\left(\mathrm{mod}m\right)$ is not negligible. In addition, increasing the average number of dark counts slightly increases the probability of error for all the strategies considered, even though no significant effects are detected for the considered range of values of $\langle N_{\mathrm{dc}}\rangle$.

In Figure 5, we show the number of counts at the H and V detectors from a simulated experiment. We can see a significant reduction of the fluctuations in the V detector, which is also marked by the significant difference in the probability of error $p_e^H$ and $p_e^V$. The main reason is that the counts in the V detector are affected only by the randomness due to the dark counts (if present), while in the H detector the expected number of photons contributes to the randomness of the outcomes as well. We have also reported the results for words of length $k\left(\mathrm{mod}m\right)=2$, which are are significantly separated from $N_{\mathrm{c}}^x\left(m\right)$ and $N_{\mathrm{c}}^x\left(k_1\right)$ as the value of $\langle N_{\mathrm{c}}\rangle$ considered is much larger than the threshold given in (22) and (23).

7. Conclusions

In this work, we have presented an enhanced photonic implementation of 1qfa for the recognition of unary language that significantly improves the performance obtained by the one originally proposed in [6]. The protocol uses the polarization degree of freedom of single photons, and exploits the possibility of detecting not only the horizontal polarization, as in [6], but also the vertical one. The resulting scheme largely outperforms the original automaton for smaller values of the mean number of sent photon $\langle N_c\rangle$. In addition, we have extended the results previously found with a detailed analysis of the conditions for which such 1qfa can work with high reliability. We have evaluated the minimum number of photons that must be sent in order to solve faithfully the inherent binary discrimination problem. As one would expect, the minimum $\langle N_c\rangle$ is smaller for the automaton that relies on the new strategy based on the V detector.

In our analysis, we have discussed the presence of dark counts in the detection of both strategies, and we have evaluated their effects both on the probability of error and on the minimum $\langle N_c\rangle$. Eventually, we also examined a joint strategy in which we combine both the H and the V detection, which can indeed be used at no additional cost. We have therefore proved that when the number of sent photon is constrained to small values, the V detection version of the 1qfa should be preferred.

Our results pave the way to the effective implementation of 1qfa using quantum optical platform, thus opening the possibility of processing strings of input symbols using feasible devices and, in turn, to introduce quantum languages and compare the complexity of classes of languages in classical and quantum cases. More generally, as the assessment of the actual power of quantum computers is one of the most significant challenges of quantum technology, implementing quantum automata provides a relevant arena to better understand the computing capabilities offered by quantum devices.