Photonic realization of a quantum finite automaton

We describe a physical implementation of a quantum finite automaton that recognizes a well-known family of periodic languages. The realization exploits the polarization degree of freedom of single photons and their manipulation through linear optical elements. We use techniques of confidence amplification to reduce the acceptance error probability of the automaton. It is worth remarking that the quantum finite automaton we physically realize is not only interesting per se but it turns out to be a crucial building block in many quantum finite automaton design frameworks theoretically settled in the literature.

Figure 1

Schematic diagram of the “hardware” of a one-way deterministic finite automaton (1dfa). The 1dfa is made of a read-only input tape consisting of a sequence of cells, each one capable of storing a symbol. The tape may be scanned by a “head”, which is moving one position right at each step. At each stage of the computation of $A$, a finite state control is in a state from a finite set $Q$.

Figure 2

The state graph for the 1dfa $A$ accepting the language $L_m$.

Figure 3

The state graph of a 1nfa for the language $E_k$.

Figure 4

The state graph of the 1pfa $A$ for the language $L_{m·n}$.

Figure 5

Scheme of the 1qfa $\mathcal{A}$ accepting the language $L_m$: Given the initial automaton state $\zeta$ and the input word $a^k$ the automaton outputs “1” (accepted) or “0” (not accepted). See the text for details.

Figure 6

(a) Two-dimensional representation of the polarization states $|H\rangle$ (horizontal polarization) and $|V\rangle$ (vertical polarization) of a single photon. We also report the representation of the single-photon state with (linear) polarization at the angle $\theta$. (b) The square of the projections along the horizontal and the vertical axes correspond to the probability of finding the photon with horizontal and vertical polarization, respectively.

Figure 7

Sketch of the photonic implementation of the 1qfa $\mathcal{A}$ accepting the language $L_m$. Single photons are generated in the polarization state $|H\rangle$ and then they pass through $k$ polarization rotators, $k$ being the length of the input word $a^k$. Each rotator implements the operator $R(\pi /m)$ rotating the polarization by the amount $\pi /m$: The overall polarization rotation is $\theta =\pi k/m$. Finally, the photons are addressed to two photodetectors by means of a polarizing beam splitters (PBS) according to their horizontal ($H$) or vertical ($V$) polarization.

Figure 8

Error probability (wrong acceptance probability) of the 1qfa $\mathcal{A}$ accepting the language $L_m$, for different values of $m$, as a function of the average number of counts $\langle N_c\rangle$.

Figure 9

Schematic diagram of the experimental setup. A 405-nm continuous wave (cw) laser diode (L) generates a pump beam which passes through an amplitude modulator, composed of a half-wave plate ($\lambda /2$) and a polarizing beamsplitter cube (PBS), and through another half-wave plate to set the polarization. The beam interacts with a 1-mm-long barium borate (BBO) crystal generating photons at 810 nm via parametric down conversion (PDC). The two beams separated by the horizontal plane are called signal and idler: On the signal's branch there are two polarizers (P) separated by a half-wave plate. Photons are finally focused into two multimode fibers through two couplers (C), and sent to homemade single-photon counting modules.

Figure 10

Experimental ratio $N_c\left(k\right)/\langle N_c\rangle$ with $k=m=5$ (green disks) and $k=1$ (red circles) as a function of the experimental run number (Rep), $k$ being the length of the input word $a^k$ of the 1qfa $\mathcal{A}$ accepting the language $L_m$. We considered different values of the overall average number of counts: (a) $\langle N_c\rangle =36$, (b) $\langle N_c\rangle =108$, (c) $\langle N_c\rangle =479$, and (d) $\langle N_c\rangle =1845$. The horizontal lines are the threshold values $N_{\mathrm{th}}$ given in Eq. (21). In the plots, we also report the theoretical error probability from Eq. (23). The reduction of the relative statistical fluctuations is evident.

Figure 11

Examples of the experimental number of counts $N_c\left(k\right)$ (dots) as a function of the length $k$ of the input word $a^k$ (we have chosen 10 values of $k$ randomly in the interval $[1,500]$). The horizontal lines refer to the threshold $N_{\mathrm{th}}$ on the number of counts for the discrimination strategy (see the text for details): If $N_c\left(k\right)\ge N_{\mathrm{th}}$ the word $a^k$ is accepted. The color of the vertical bars refers to the theoretical acceptance (green) or rejection (red) of the corresponding input $a^k$ by the 1qfa $\mathcal{A}$ accepting the language $L_m$, with $m=23$. The average number of counts is $\langle N_c\rangle =18439\pm 114$ (top panel, corresponding to $N_{\mathrm{th}}=18267.5$) and $\langle N_c\rangle =56477\pm 244$ (bottom panel, leading to $N_{\mathrm{th}}=55951.5$). In both panels, the lower plots are a magnification of the region around the threshold $N_{\mathrm{th}}$. (Top panel) In this case, the error probability evaluated from Eq. (23) is $p_{\mathrm{err}}=10.3\%$. The number 229 is accepted according to our strategy, since the number of counts (see the orange arrows) is larger than the threshold (horizontal solid line), but it should be rejected; on the other hand, the number 115 should be accepted but it is rejected since the number of counts (see the magenta arrows) is below the threshold. (Bottom panel) Here the error probability evaluated from Eq. (23) is $p_{\mathrm{err}}=1.3\%$. Now the number 229 is rejected and the number 115 is accepted, according to the definition of $L_m$. See the text for details.