# Efficient Quantum Circuit Cutting by Neglecting Basis Elements

Daniel T. Chen1, Ethan H. Hansen1, Xinpeng Li1, Vinooth Kulkarni1,
Vipin Chaudhary1, Bin Ren3, Qiang Guan2, Sanmukh Kuppannagari1, Ji Liu4, Shuai
Xu1 This research was supported in part by NSF Award 2216923. 1 Department of
Computer and Data Science
Case Western Reserve University, Cleveland, OH 44106
Email: {txc461, ehh50, xxl1337, vxk285, vxc204, sxk1942<EMAIL_ADDRESS>2
Department of Computer Science
Kent State University, Kent, OH 44240
Email<EMAIL_ADDRESS>3 College of William & Mary, Williamsburg, VA 23185
Email<EMAIL_ADDRESS>4 Argonne National Laboratory, IL 60439
Email<EMAIL_ADDRESS>
###### Abstract

Quantum circuit cutting has been proposed to help execute large quantum
circuits using only small and noisy machines. Intuitively, cutting a qubit
wire can be thought of as classically passing information of a quantum state
along each element in a basis set. As the number of cuts increase, the number
of quantum degrees of freedom needed to be passed through scales
exponentially. We propose a simple reduction scheme to lower the classical and
quantum resources required to perform a cut. Particularly, we recognize that
for some cuts, certain basis element might pass “no information” through the
qubit wire and can effectively be neglected. We empirically demonstrate our
method on circuit simulators as well as IBM quantum hardware, and we observed
up to 33 percent reduction in wall time without loss of accuracy.

##  I Introduction

While quantum computers can provide exponential speed-up for certain
algorithms, unveiling potential diverse and disruptive applications [1, 2, 3],
current quantum hardware lacks the scale and reliability to execute these
quantum circuits. Preskill described such hardware as Noisy Intermediate-Scale
Quantum (NISQ) computers, and much effort has been focused on increasing qubit
fidelity and qubit count [4, 5, 6, 7]. Meanwhile, algorithmic developments
such as variational quantum algorithms [8, 9, 10] have caught substantial
attention for having the potential to realize quantum advantage utilizing only
NISQ machines. However, there are few results demonstrating provable advantage
for using variational quantum algorithms over known classical algorithms [11].

A natural question to ask when given limited qubits is: “Are there ways of
simulating large quantum circuits using small quantum devices?” Inspired by
fragmentation methods in molecular simulations [12, 13, 14, 15], Peng et al.
has demonstrated that it is possible to divide quantum circuit into
subcircuits, or fragments, that can be independently executed on small quantum
computers and then recombined [16]. This method does not impose assumptions on
circuits but requires a large amount of classical computing
resources—exponential in the number of cuts—in order to reconstruct the
expected output of the respective uncut circuit.

Nonetheless, quantum circuit cutting still holds great promise as an effective
tool for realizing quantum algorithms. Most notably, it has been empirically
shown that reducing the circuit size, even when sufficiently large machines
are available, can improve fidelity [17, 18, 19]. Moreover, tailoring circuit
cutting to specific applications, e.g. combinatorial optimization [20] and
error mitigation [21], can effectively avoid the exponential classical
overhead. Alternatively, stochastic methods through randomized measurement
[22] and sampling [23] have also been developed to reduce the postprocessing
cost. In recent, state-of-the-art research, it has been empirically shown that
optimization can be employed to replace traditional tomographic techniques and
significantly reduce the classical resources needed for reconstruction, though
at the cost of additional circuit evaluations [24]. Circuit cutting algorithms
have also undergone improvement and variations in terms of performance.
Maximum likelihood methods have been introduced to circuit cutting to formally
account for finite-shot error [19]. Shadow tomography—an efficient classical
representation of quantum states for predicting expectations of observables
[25]—can also be applied to individual circuit fragments [26].

Figure 1: Circuit diagram corresponding to the 3-qubit example

Our work contributes in the direction of reducing the computational resources
needed. In this paper, we introduce the idea of a golden cutting point: a cut
location on a quantum circuit where a certain measurement basis can be
neglected, e.g., when the quantum state operates in a lower-dimensional
subspace prior to the cut. Such reduction lowers the runtime of reconstructing
measurement statistics from fragments by approximately 33% for a single cut
and avoids excessive circuit executions. We experimentally verify our method
on both the Qiskit Aer simulator [27] and superconducting quantum devices from
IBM [28].

The outline of this paper is as follows. Section II presents the mathematical
formulation behind quantum circuit cutting and the idea of golden cutting
points. We begin with an elaborate three-qubit example in Section II-A and
generalize it to arbitrary circuit bipartitions in Section II-B. Then, we
proceed to conduct numerical experiments in Section III. Finally, we provide
insight into future directions in Section IV.

##  II Quantum Circuit Cutting

Quantum circuit cutting seeks a qubit wire (or multiple qubit wires) such
that, upon removing, the circuit decomposes into several independent
fragments. This is accomplished by performing quantum tomography—learning a
quantum state—on the qubit upstream of the cut and recreating the inferred
state in the downstream qubit. One can think of tomography as estimating the
coefficient after expanding a quantum state with respect to some basis set,
which we take to be the Pauli basis

$\displaystyle\bigg{\\{}I=\begin{pmatrix}1&0\\\ 0&1\end{pmatrix},~{}~{}$
$\displaystyle X=\begin{pmatrix}0&1\\\ 1&0\end{pmatrix},$ $\displaystyle
Y=\begin{pmatrix}0&-i\\\ i&0\end{pmatrix},~{}~{}Z=\begin{pmatrix}1&0\\\
0&-1\end{pmatrix}\bigg{\\}}$ (1)

for concreteness. By measuring the quantum state with respect to each element
in the basis, one could piece together the state prior to the cut. Then, by
initializing the downstream qubit incident to the cut into the eigenstate of
each element in the basis, one could learn the behavior of the circuit given
the initial state. Lastly, reweighting the results obtained through multiple
initializations yields the behavior of an uncut circuit.

If a circuit undergoes $K$ cuts, tomography has to be performed on all $K$
qubits at the location of the cuts. The set of length-$K$ Pauli strings is
then an appropriate basis for a $K$-qubit system and the measurement-
preparation scheme described above must be done for all elements in the set.
Thus, the cost of performing circuit cutting scales exponentially with the
number of cuts. In this section, we introduce a special class of circuits that
contains a golden cutting point and that enjoys a reduction in measurement
complexity and classical postprocessing cost. We will demonstrate this via a
three-qubit example (Section II-A) and proceed to formalize the phenomenon for
arbitrary circuit bipartitions (Section II-B).

###  II-A A Three-qubit Example

Consider the following three-qubit state

$\displaystyle\rho=U_{23}U_{12}|000\rangle\langle
000|U_{12}^{\dagger}U_{23}^{\dagger}$ (2)

where unitaries $U_{12}$ and $U_{23}$ can be arbitrary quantum gates (Figure
1). Notice that the qubit wire between the two gates can be cut, in the sense
that we can rewrite the above state as

$\displaystyle\rho=\frac{1}{2}\sum_{M_{2}\in\mathcal{B}}\rho_{f_{1}}(M_{2})\otimes\rho_{f_{2}}(M_{2})$
(3)

where the set $\mathcal{B}=\\{I,X,Y,Z\\}$ is the Pauli basis, and

$\displaystyle\rho_{f_{1}}(M_{2})$
$\displaystyle=\textnormal{tr}_{2}(M_{2}U_{12}|00\rangle\langle
00|U_{12}^{\dagger}),$ (4) $\displaystyle\rho_{f_{2}}(M_{2})$
$\displaystyle=U_{23}(M_{2}\otimes|0\rangle\langle 0|)U_{23}^{\dagger}.$ (5)

Here, $M_{2}$ refers to applying the operator $M$ onto to the second qubit.
This convention will be held throughout the manuscript where numerical
subscripts denote the qubit(s) an operator is acting on.

However, as currently presented, the fragments are not quantum states as Pauli
matrices are traceless operators. To obtain a physical interpretation,
consider the eigendecomposition eigendecomposition $M=rM^{r}+sM^{s}$ for each
$M\in\mathcal{B}$ where $r,s\in\\{+1,-1\\}$ are the eigenvalues and
$M^{r},M^{s}$ are the eigenstates. Then, we can rewrite Equation 3 as

$\displaystyle\rho=\frac{1}{2}\sum_{\begin{subarray}{c}M_{2}\in\mathcal{B}\\\
r,s=\pm
1\end{subarray}}rs\rho_{f_{1}}(M_{2}^{r})\otimes\rho_{f_{2}}(M_{2}^{s}).$ (6)

The eigenstates of $M\in\mathcal{B}$ have unit trace and can be regarded as
quantum states.

Intuitively, one can understand circuit cutting as classically passing
information through the qubit wire that is cut. Inside the summation (fix an
$M_{2}$ of choice), the information stored in the second qubit in the
direction $M_{2}$ is measured—taking the partial trace in $\rho_{f_{1}}$—and
passed onto the remaining circuit—initializing into state $M_{2}^{s}$. Since
the circuit fragments $\rho_{f_{1}}$ and $\rho_{f_{2}}$ can be simulated
independently, through repeating the measurement-initialization scheme, we can
effectively cut the original circuit, run fragments in parallel, and combine
the results classically.

We are often interested in finding the expectation of the quantum state with
respect to a quantum observable, $O$. Without loss of generality, assume an
observable can be decomposed as $O=O_{1}\otimes O_{23}$. Then, we can rewrite
the expectation in terms of $\rho_{f_{1}}$ and $\rho_{f_{2}}$:

$\displaystyle\textnormal{tr}(O\rho)$
$\displaystyle=\frac{1}{2}\sum_{M_{2},r,s}rs~{}\textnormal{tr}(O_{1}\rho_{f_{1}}(M_{2}^{r}))\textnormal{tr}(O_{23}\rho_{f_{2}}(M_{2}^{s}))$
(7)
$\displaystyle=\frac{1}{2}\sum_{M_{2},s}s~{}\textnormal{tr}(O_{23}\rho_{f_{2}}(M_{2}^{s}))\sum_{r}r~{}\textnormal{tr}(O_{1}\rho_{f_{1}}(M_{2}^{r})).$
(8)

The above summation involves 16 terms. Experimentally, the summation requires
measuring the second qubit in the fragment upstream for each non-identity
Pauli basis and initializing the first qubit in the downstream fragment to the
respective eigenstates.

However, the computation above can potentially be reduced. Suppose that there
exists an $M_{2,*}\in\mathcal{B}$ such that the last summation evaluates to
zero, that is,

$\displaystyle\sum_{r=\pm
1}r~{}\textnormal{tr}\left(O_{1}\rho_{f_{1}}(M_{2,*}^{r})\right)=0.$ (9)

Note that this can happen one of two ways:

  1. (i)

Operator $O_{1}$ is orthogonal to the conditional state
$\rho_{f_{1}}(M_{2,*}^{r})$, i.e.,
$\textnormal{tr}(O\rho_{f_{1}}(M_{2,*}^{r}))=0$ for both $r=\pm 1$. For
example, $O_{1}=X$ and $U_{12}|00\rangle=(|00\rangle+|11\rangle)/\sqrt{2}$,
the Bell state.

  2. (ii)

The conditional state is in a subspace that “conveys no information” about the
observable, specifically, $\textnormal{tr}(O_{1}\rho_{f_{1}}(M_{2,*}^{r}))\neq
0$ but the weighted sum in Equation 9 leads to systematic cancellations. For
example, $O_{1}=|+\rangle\langle+|$ is a projector to the plus-state, and
$U_{12}|00\rangle$ is again the Bell state.

Upon noting the reduction, the number of terms in the summation drops from 16
to 12. Moreover, since any term involving $M_{2,*}$ is neglected, there is no
need to estimate the expectation in the downstream fragment
($\textnormal{tr}\left(O_{23}\rho_{f_{2}}(M_{2,*}^{s})\right)$), which saves
circuit evaluations that use the initial state $M_{2,*}^{s}$. We say that the
cut is a golden cutting point if such reduction occurs.

###  II-B Generalization

We formally extend the above case to more general bipartitions, but refrain
from considering cutting schemes that result in more than three fragments
(c.f. [26] for general expression of expectations with respect to circuit
fragments). Suppose a $N$-qubit quantum circuit induces a state $\rho$. A set
of $K$ cuts, with injective function $c$ mapping the $i$-th cut onto qubit
$c(i)\in[N]=\\{1,2,\dots,N\\}$. By cutting the $K$ wires, the circuit can be
bipartitioned into fragments $f_{1}$ and $f_{2}$. Now, cutting requires
passing information from $K$ sets of basis $\mathcal{B}$ through the cutting
point, namely, measuring upstream qubits and preparing downstream qubits with
respect to operators

$\displaystyle\bm{M}=\begin{pmatrix}M_{c(1)}&M_{c(2)}&\dots&M_{c(K)}\end{pmatrix}\in\mathcal{B}^{K}.$
(10)

Furthermore, each operator $M$ admits spectral decomposition. Letting

$\displaystyle\bm{r}=\begin{pmatrix}r_{c(1)}&r_{c(2)}&\dots&r_{c(K)}\end{pmatrix}\in\\{-1,+1\\}^{K}$
(11)

be a tuple of eigenvalues, we define

$\displaystyle\bm{M}^{\bm{r}}=\begin{pmatrix}M_{c(1)}^{r(1)}&M_{c(2)}^{r(2)}&\dots&M_{c(K)}^{r(K)}\end{pmatrix}$
(12)

to be the $\bm{r}$-th eigenstate of operator $\bm{M}$.

Using the above notation, we can compactly write the uncut state using the
fragment-induced states $\rho_{f_{i}}(\bm{M})$ for $i=1,2$. Following Equation
6 gives the reconstruction formula in this bipartition case:

$\displaystyle\rho=\frac{1}{2^{K}}\sum_{\begin{subarray}{c}\bm{M}\in\mathcal{B}^{K},\\\
\bm{r},\bm{s}\in\\{-1,+1\\}^{K}\end{subarray}}\prod_{i\in[K]}r_{i}s_{i}~{}\rho_{f_{1}}(\bm{M}^{\bm{r}})\otimes\rho_{f_{2}}(\bm{M}^{\bm{s}}).$
(13)

Alternatively, for any desired quantum observable $O$, suppose the operator
can be decomposed to accommodate the two fragments, i.e., $O=O_{f_{1}}\otimes
O_{f_{2}}$ up to appropriate permutation of qubit indices. This is without
loss of generality as expansions using Pauli strings would yield a linear
combination of operators that are qubit-wise separable. Then, we can arrive at
an expression analogous to Equation 7 in terms of the fragments $\rho_{f_{i}}$
and their respective observables $O_{f_{i}}$:

$\displaystyle\textnormal{tr}(O\rho)=$
$\displaystyle\frac{1}{2^{K}}\sum_{\bm{M},\bm{r},\bm{s}}\prod_{i\in[K]}r_{i}s_{i}~{}\textnormal{tr}\left(O_{f_{1}}\rho_{f_{1}}(\bm{M}^{\bm{r}})\right)\textnormal{tr}\left(O_{f_{2}}\rho_{f_{2}}(\bm{M}^{\bm{s}})\right).$
(14)

We now formally define the golden circuit cutting point.

######  Definition 1.

A $N$-qubit circuit amenable to bipartition with $K$ cuts has a _golden
cutting point_ if there exists $k^{*}\in[K]$ such that

$\displaystyle\sum_{r_{c(k^{*})}}r_{c(k^{*})}~{}\textnormal{tr}\left(O_{f_{1}}\rho_{f_{1}}(\bm{M}^{\bm{r}})\right)=0.$
(15)

Note that golden cutting points are not necessarily unique. There can be
multiple cuts with negligible bases and/or multiple negligible bases in one
cut. Suppose there are $K_{g}$ many golden cutting points and $K_{r}=K-K_{g}$
regular cutting points, the run time complexity of reconstructing the
expectation in this bipartite case scales as
$\mathcal{O}(4^{K_{r}}3^{K_{g}})$. Moreover, there is no need of preparing the
downstream fragments into the respective eigenstates, reducing the number of
circuit evaluations from $\mathcal{O}(6^{K})$ to
$\mathcal{O}(6^{K_{r}}4^{K_{g}})$. It is worth noting that the eigenstate
preparation scheme is overcomplete and alternative bases, e.g. the symmetric
informationally-complete (SICC) basis, can be used to achieve
$\mathcal{O}(4^{K})$ circuit evaluations without invoking golden circuit
cutting formalism. However, employing the SICC basis would require more
involved implementation, namely, solving linear systems, in order to construct
the appropriate tensor during reconstruction.

We emphasize that golden cutting points as its current form is strictly a
product of circuit design. That is, we can design circuits that admits golden
cutting points at known locations (c.f. Section III). In reality, the
existence of golden cutting points depends on the choice of the observable
$O$, how it can be decomposed into form amendable to cutting, and the the
state of the qubit prior to the cut. It is unlikely that an arbitrary circuit
would exhibit such property without intricate designs, and we defer further
discussion on finding golden cutting points to Section IV.

##  III Experiments

Figure 2: Example 5-qubit circuit with golden cutting point. $U_{1}$ and
$U_{2}$ are randomized circuits. Note that other odd-number circuit widths
were used too, mainly 7-qubits split into subcircuits of 4 qubits each.

We demonstrate the capability of golden cutting points numerically.
Specifically, experiments were designed to verify two aspects of our work:
first, that our method does not sacrifice the correctness of reconstruction
and second, that our method reduces the overall runtime of the algorithm. The
circuit used in our experiment takes the form showed in Figure 2 where the
sizes of the circuits were tailored to the size of the device it was run on.
Most commonly, we split 5- and 7-qubit circuits into fragments of 3 and 4
qubits respectively. In addition to quantum hardware, we also tested our
method on the Aer simulator from Qiskit [27].

The generated circuits featured collections of $RX$ gates with the rotation
angle $\theta$ was chosen uniformly at random from the interval $[0,6.28]$, as
well as random gates generated using the `random_circuit()` function in
Qiskit, denoted by $U_{1}$ and $U_{2}$ in Figure 2. In our experiments, we
want to acquire the bitstring probability distribution generated by repeated
measurements in the computational ($Z$) basis. Alternatively, to match the
formalism of Section II-B, for all bitstrings $\hat{b}\in\\{0,1\\}^{n}$, one
can interpret the above as estimating the expectation of the projector
observable $\Pi^{\hat{b}}=|\hat{b}\rangle\langle\hat{b}|$ where $n=5,7$ is the
number of qubits in a circuit. This observable decomposes straightforwardly
upon cutting:

$\displaystyle\Pi^{\hat{b}}=\Pi^{\hat{b}_{1}}\otimes\Pi^{\hat{b}_{2}}$ (16)

where $\hat{b}_{1}$ and $\hat{b}_{2}$ are bitstrings of length $\lfloor
n/2\rfloor$ and $\lceil n/2\rceil$ respectively such that the concatenation
recovers $\hat{b}$. By repeating many measurements in the computational basis
and obtaining a bitstring distribution, we can then estimate the expectation
of the projector observables. The restrictions imposed on our circuit ansatz
creates a golden cutting point. In particular, the contribution of first
fragment to the total expectation (with respect to the projector operator
above, which has only diagonal components) conditioned on observing each
eigenstate of the Pauli $Y$ operator leads to components of equal magnitudes.
Once weighed by the respective eigenvalues, the trace terms systematically
cancels and induces a golden cutting point as defined in 15.

###  III-A Verifying Reconstruction Accuracy

Figure 3: Comparison of weighted distances for uncut circuit evaluations and
reconstructed meausurements from fragment data. Each bar was averaged over 10
independent trials. Each trial consisted of 10,000 shots per fragment. Error
bars represent 95% confidence intervals.

We first proceed to verify the correctness of our golden cutting point method.
We performed noiseless (in the sense of hardware noise) simulations of the
full uncut circuit to obtain the ground truth distribution and compared our
golden cutting point method to it. In addition, we ran the same circuits, both
uncut and fragmented, on superconducting IBM Quantum devices [28]. To compare
distributions, we now introduce a weighted distance function $d_{w}$:

$\displaystyle
d_{w}(p;q)=\sum_{x\in\mathcal{X}}\frac{\left(p(x)-q(x)\right)^{2}}{q(x)}.$
(17)

for distributions $p$ and $q$ with support $\mathcal{X}$. In the experiment,
$p$ was our “test” distribution and $q$ was the “ground truth.” This weighted
distance function penalizes large percentage deviations more than other
metrics such as the total variational distance.

Using this weighted distance function, we determined the distance between the
ground truth bitstring distribution from the Aer simulator and the
distribution obtained by running the full circuit on quantum hardware. We then
also determined the distance between the ground truth distribution and the
distribution obtained by running our golden cutting method on quantum
hardware. We repeated the experiment for machines of two different sizes—a
5-qubit device would run a 5-qubit circuit that is split into two 3-qubit
subcircuits and a 7-qubit device would run a 7-qubit circuit split into two
4-qubit subcircuits. Each circuit configuration was repeated for 10 trials
with each trial consisting of 10,000 shots per (sub)circuit. The results of
the experiments are shown in Figure 3.

Because previous work has found that quantum circuit cutting has yielded a
benefit in terms of fidelity, we expected similar results. We were surprised
to find that such a benefit is non-existent on 5-qubit devices and not
detectable within 95% confidence intervals on a 7-qubit device. This is likely
due to the fact that our circuits were not particularly deep—only a few gates
in each. As the circuit depth increases we should expect to see more of a
benefit from circuit cutting. Additionally, an average of only 10 trials was
performed, leaving our uncertainties relatively large. In our future work we
will run more trials, potentially on larger devices, or with greater depths,
to more precisely determine the true distance for this method. Regardless, in
this work, we have verified that (within error) our method performs as well as
full circuit execution on real hardware in terms of outputting the correct
bitstring distribution.

Figure 4: Runtime comparison of circuits with (in gold) and without (in red)
golden circuit cutting optimization. Each configuration was repeated for 1000
trials and each trial involved 1000 shots for each (sub)circuit. Error bars
represent 95% confidence intervals.

###  III-B Algorithm runtime

The presented golden cutting point method predicts a reduction in the number
of measurements, thereby lowering the runtime of the procedure. In this
experiment, we recorded the time taken for gathering fragment data and
reconstructing them on a randomly generated circuit. We assumed the golden
cutting point was known a priori (see Section IV for determining the existence
of golden cutting points), and studied the runtime reduction from exploiting
this knowledge. The results are illustrated in Figure 4.

Figure 5: Circuit cutting runtime with and without golden cutting point on
quantum devices from IBM. Each bar represents the average runtime of 50 trials
and each trial comprised of 1,000 shots for each (sub)circuit.

We then repeated the same experiment using real devices available through the
IBM Quantum Experience [28]. We report a speedup of 33 percent using our
method as compared to the standard method [18], as shown in Figure 5.
Specifically, we find that the average time for execution using the standard
(without golden cutting point consideration) reconstruction method was 18.84
seconds whereas the golden cutting point method had a mean of 12.61 seconds.
This reduction in run time is largely attributed to the reduced number of
circuit evaluations. Particularly, we avoided having to execute a third of the
total shots by neglecting one basis element, bringing the total number of
circuit executions down from $4.5\times 10^{5}$ to $3.0\times 10^{5}$. This
demonstrates the applicability of our method: it is simple to implement and
produces a considerable reduction in wall time needed to perform circuit
reconstruction.

##  IV Conclusion

In this paper, we introduced the idea of a golden cutting point where elements
of a basis set can be neglected (Section II-B). Neglecting these basis
elements allows for a considerable decrease in the runtime. The reduction can
be attributed to (1) fewer terms are involved when combining measurement
results from fragments, and (2) fewer circuit evaluations are needed in the
fragment downstream of the golden cut. We verified the correctness and
demonstrated the lowered runtime in both simulators and real quantum hardware
(Section III). We observed that golden cutting points do not come at the cost
of accuracy, and a statistically significant 33% decrease in runtime persists
in both a simulated environment and quantum devices.

The introduction of the golden cutting point begs the question of applicable
algorithms that have built-in golden cutting points. Variational circuits are
a potential candidate due to their flexibility in the circuit ansatz. Although
variational algorithms for combinatorial optimization or chemical simulations
have great structural assumptions given by the Hamiltonian, quantum machine
learning circuits typically do not possess these constraints and therefore are
likely more amenable to exploiting the golden cutting point formalism.

Moreover, detection of the existence of a golden cutting point is also an
interesting one. In this work, we assumed the golden cutting point was known a
priori. However, it is not obvious whether a basis can be neglected without
simulating the circuit. Thus, we suspect there are methods for detecting
golden cutting points “online” during the execution of the circuit cutting
procedure through sequential empirical measurements. Note that this does not
necessarily sacrifice the parallelism of circuit cutting as golden cutting
points only affect the fragments directly incident to the cut. However,
performing such a method would require further statistical analysis of
acceptable error and the amplification of error through tensor contraction.

## Acknowledgements

We acknowledge the use of IBM Quantum services for this work. The views
expressed are those of the authors, and do not reflect the official policy or
position of IBM or the IBM Quantum team. This material is based upon work
supported by the U.S. Department of Energy, Office of Science, National
Quantum Information Science Research Centers. The colors used in figures were
based on Nord Theme [29]. Daniel T. Chen and Ethan H. Hansen contributed
equally to this work.

## References

  * [1] L. K. Grover, “A fast quantum mechanical algorithm for database search,” in _Proceedings of the twenty-eighth annual ACM symposium on Theory of computing_ , ser. STOC ’96. Association for Computing Machinery, 1996, pp. 212–219. [Online]. Available: https://doi.org/10.1145/237814.237866
  * [2] P. W. Shor, “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,” _SIAM Journal on Computing_ , vol. 26, no. 5, pp. 1484–1509, oct 1997. [Online]. Available: https://doi.org/10.1137%2Fs0097539795293172
  * [3] A. Robert, P. K. Barkoutsos, S. Woerner, and I. Tavernelli, “Resource-efficient quantum algorithm for protein folding,” _npj Quantum Information_ , vol. 7, no. 1, feb 2021. [Online]. Available: https://doi.org/10.1038%2Fs41534-021-00368-4
  * [4] R. LaRose, A. Mari, S. Kaiser, P. J. Karalekas, A. A. Alves, P. Czarnik, M. E. Mandouh, M. H. Gordon, Y. Hindy, A. Robertson, P. Thakre, M. Wahl, D. Samuel, R. Mistri, M. Tremblay, N. Gardner, N. T. Stemen, N. Shammah, and W. J. Zeng, “Mitiq: A software package for error mitigation on noisy quantum computers,” _Quantum_ , vol. 6, p. 774, aug 2022. [Online]. Available: https://doi.org/10.22331%2Fq-2022-08-11-774
  * [5] M. H. Abobeih, Y. Wang, J. Randall, S. J. H. Loenen, C. E. Bradley, M. Markham, D. J. Twitchen, B. M. Terhal, and T. H. Taminiau, “Fault-tolerant operation of a logical qubit in a diamond quantum processor,” _Nature_ , vol. 606, no. 7916, pp. 884–889, may 2022. [Online]. Available: https://doi.org/10.1038%2Fs41586-022-04819-6
  * [6] A. A. Saki, A. Katabarwa, S. Resch, and G. Umbrarescu, “Hypothesis testing for error mitigation: How to evaluate error mitigation,” 2023. [Online]. Available: https://arxiv.org/abs/2301.02690
  * [7] J. Gambetta, “Quantum-centric supercomputing: The next wave of computing,” Dec 2022. [Online]. Available: https://research.ibm.com/blog/next-wave-quantum-centric-supercomputing
  * [8] M. Cerezo, A. Arrasmith, R. Babbush, S. C. Benjamin, S. Endo, K. Fujii, J. R. McClean, K. Mitarai, X. Yuan, L. Cincio, and P. J. Coles, “Variational quantum algorithms,” _Nature Reviews Physics_ , vol. 3, no. 9, pp. 625–644, aug 2021. [Online]. Available: https://doi.org/10.1038%2Fs42254-021-00348-9
  * [9] E. Farhi, J. Goldstone, and S. Gutmann, “A quantum approximate optimization algorithm,” _arXiv preprint arXiv:1411.4028_ , 2014. [Online]. Available: https://arxiv.org/abs/1411.4028
  * [10] D. A. Fedorov, B. Peng, N. Govind, and Y. Alexeev, “VQE method: a short survey and recent developments,” _Materials Theory_ , vol. 6, no. 1, pp. 1–21, 2022. [Online]. Available: https://doi.org/10.1186/s41313-021-00032-6
  * [11] B. Barak and K. Marwaha, “Classical Algorithms and Quantum Limitations for Maximum Cut on High-Girth Graphs,” in _13th Innovations in Theoretical Computer Science Conference (ITCS 2022)_ , ser. Leibniz International Proceedings in Informatics (LIPIcs), M. Braverman, Ed., vol. 215. Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022, pp. 14:1–14:21. [Online]. Available: https://drops.dagstuhl.de/opus/volltexte/2022/15610
  * [12] A. Warshel and M. Levitt, “Theoretical studies of enzymic reactions: dielectric, electrostatic and steric stabilization of the carbonium ion in the reaction of lysozyme,” _Journal of molecular biology_ , vol. 103, no. 2, pp. 227–249, 1976. [Online]. Available: https://www.sciencedirect.com/science/article/pii/0022283676903119
  * [13] M. S. Gordon, D. G. Fedorov, S. R. Pruitt, and L. V. Slipchenko, “Fragmentation methods: A route to accurate calculations on large systems,” _Chemical reviews_ , vol. 112, no. 1, pp. 632–672, 2012. [Online]. Available: https://doi.org/10.1021/cr200093j
  * [14] W. Li, S. Li, and Y. Jiang, “Generalized energy-based fragmentation approach for computing the ground-state energies and properties of large molecules,” _The Journal of Physical Chemistry A_ , vol. 111, no. 11, pp. 2193–2199, 2007\. [Online]. Available: https://doi.org/10.1021/jp067721q
  * [15] H. Li, W. Li, S. Li, and J. Ma, “Fragmentation-based QM/MM simulations: Length dependence of chain dynamics and hydrogen bonding of polyethylene oxide and polyethylene in aqueous solutions,” _The Journal of Physical Chemistry B_ , vol. 112, no. 23, pp. 7061–7070, 2008. [Online]. Available: https://doi.org/10.1021/jp800777e
  * [16] T. Peng, A. W. Harrow, M. Ozols, and X. Wu, “Simulating large quantum circuits on a small quantum computer,” _Physical Review Letters_ , vol. 125, no. 15, oct 2020. [Online]. Available: https://doi.org/10.1103%2Fphysrevlett.125.150504
  * [17] T. Ayral, F.-M. Le Régent, Z. Saleem, Y. Alexeev, and M. Suchara, “Quantum divide and compute: Hardware demonstrations and noisy simulations,” in _2020 IEEE Computer Society Annual Symposium on VLSI (ISVLSI)_. IEEE, 2020, pp. 138–140. [Online]. Available: https://ieeexplore.ieee.org/document/9155024
  * [18] T. Ayral, F.-M. L. Régent, Z. Saleem, Y. Alexeev, and M. Suchara, “Quantum divide and compute: exploring the effect of different noise sources,” _SN Computer Science_ , vol. 2, no. 3, pp. 1–14, 2021. [Online]. Available: https://doi.org/10.1007/s42979-021-00508-9
  * [19] M. A. Perlin, Z. H. Saleem, M. Suchara, and J. C. Osborn, “Quantum circuit cutting with maximum-likelihood tomography,” _npj Quantum Information_ , vol. 7, no. 1, p. 64, 2021. [Online]. Available: https://doi.org/10.1038/s41534-021-00390-6
  * [20] Z. H. Saleem, T. Tomesh, M. A. Perlin, P. Gokhale, and M. Suchara, “Quantum Divide and Conquer for Combinatorial Optimization and Distributed Computing,” _arXiv preprint_ , Jul. 2021. [Online]. Available: https://arxiv.org/abs/2107.07532
  * [21] J. Liu, A. Gonzales, and Z. H. Saleem, “Classical simulators as quantum error mitigators via circuit cutting,” _arXiv preprint arXiv:2212.07335_ , 2022\. [Online]. Available: https://arxiv.org/abs/2212.07335
  * [22] A. Lowe, M. Medvidović, A. Hayes, L. J. O’Riordan, T. R. Bromley, J. M. Arrazola, and N. Killoran, “Fast quantum circuit cutting with randomized measurements,” 2022. [Online]. Available: https://arxiv.org/abs/2207.14734
  * [23] D. Chen, B. Baheri, V. Chaudhary, Q. Guan, N. Xie, and S. Xu, “Approximate quantum circuit reconstruction,” in _2022 IEEE International Conference on Quantum Computing and Engineering (QCE)_. IEEE, 2022, pp. 509–515.
  * [24] G. Uchehara, T. M. Aamodt, and O. Di Matteo, “Rotation-inspired circuit cut optimization,” _arXiv preprint arXiv:2211.07358_ , 2022. [Online]. Available: https://arxiv.org/abs/2211.07358
  * [25] H.-Y. Huang, R. Kueng, and J. Preskill, “Predicting many properties of a quantum system from very few measurements,” _Nature Physics_ , vol. 16, no. 10, pp. 1050–1057, 2020. [Online]. Available: https://doi.org/10.1038/s41567-020-0932-7
  * [26] D. T. Chen, Z. H. Saleem, and M. A. Perlin, “Quantum divide and conquer for classical shadows,” _arXiv preprint arXiv:2212.00761_ , 2022. [Online]. Available: https://arxiv.org/abs/2212.00761
  * [27] A. tA-v et al., “Qiskit: An open-source framework for quantum computing,” 2021.
  * [28] “IBM Quantum,” 2023. [Online]. Available: https://quantum-computing.ibm.com/
  * [29] S. Greb, “Nord theme.” [Online]. Available: https://www.nordtheme.com/


# Fuzzy semigroups via semigroups

Anjeza Krakulli
Universiteti Aleksandër Moisiu
Fakulteti i Teknologjisë dhe Informacionit
Departamenti i Matematikës, Durrës
<EMAIL_ADDRESS>
Elton Pasku
Universiteti i Tiranës
Fakulteti i Shkencave Natyrore
Departamenti i Matematikës, Tiranë
<EMAIL_ADDRESS>

###### Abstract

The theory of fuzzy semigroups is a branch of mathematics that arose in early
90’s as an effort to characterize properties of semigroups by the properties
of their fuzzy subsystems which include, fuzzy subsemigroups and their alike,
fuzzy one (resp. two) sided ideals, fuzzy quasi-ideals, fuzzy bi-ideals etc.
To be more precise, a fuzzy subsemigroup of a given semigroup $(S,\cdot)$ is
just a $\wedge$-prehomomorphism $f$ of $(S,\cdot)$ to $([0,1],\wedge)$.
Variations of this, which correspond to the other before mentioned fuzzy
subsystems, can be obtained by imposing certain properties to $f$. It turns
out from the work of Kuroki, Mordeson, Malik and that of many of their
descendants, that fuzzy subsystems play a similar role to the structure theory
of semigroups that play their non fuzzy analogues. The aim of the present
paper is to show that this similarity is not coincidental. As a first step to
this, we prove that there is a 1-1 correspondence between fuzzy subsemigroups
of $S$ and subsemigroups of a certain type of $S\times I$. Restricted to fuzzy
one sided ideals, this correspondence identifies the above fuzzy subsystems to
their analogues of $S\times I$. Using these identifications, we prove that the
characterization of the regularity of semigroups in terms of fuzzy one sided
ideals and fuzzy quasi-ideals can be obtained as an implication of the
corresponding non fuzzy analogue. In a further step, we give new
characterizations of semilattices of left simple semigroups in terms of left
simple fuzzy subsemigroups, and of completely regualr semigroups in terms of
completely simple fuzzy subsemigroups. Both, left simple fuzzy subsemigroups,
and completely simple fuzzy subsemigroups are defined here for the first time,
and the corresponding characterizations generalize well known
characterizations of the corresponding semigroups.
Key words and phrases: Fuzzy subsemigroup, fuzzy one sided ideal, fuzzy quasi-
ideal, regular semigroup.

##  1 Introduction

Given a semigroup $(S,\cdot)$, a fuzzy subsemigroup of $S$ is a function
$f:S\rightarrow[0,1]$ such that for all $a,b\in S$, $f(ab)\geq f(a)\wedge
f(b)$. Thus, a fuzzy subsemigroup is just a prehomomorphism
$f:(S,\cdot)\rightarrow([0,1],\wedge)$ of semigroups. A fuzzy subsemigroup as
above will be called a fuzzy left ideal (resp. right ideal) of $S$ if for all
$a,b\in S$, $f(ab)\geq f(b)$ (resp. $f(ab)\geq f(a)$). The composite of two
fuzzy subsets $f,g:S\rightarrow[0,1]$ is given by

$(f\circ g)(a)=\left\\{\begin{array}[]{ccc}{\vee}_{a=bc}(f(b)\wedge
g(c))&if&\exists x,y\in S,a=xy\\\ 0&if&\forall x,y\in S,a\neq
xy.\end{array}\right.$

The operation $\circ$ is associative. The definition of $\circ$ is needed in
defining fuzzy quasi-ideals which are maps $q:S\rightarrow[0,1]$ such that
$q\circ S\cap S\circ q\subseteq q$. In more details, the inclusion here means
that for every $a\in S$, $(q\circ S)(a)\wedge(S\circ q)(a)\leq q(a)$, and $S$
is the fuzzy subsemigroup which maps every $a\in S$ to 1. More generally, for
every subsemigroup $A$ of $S$, the characteristic map $\chi_{A}$, defined by

$\chi_{A}(a)=\left\\{\begin{array}[]{ccc}1&if&a\in A\\\ 0&if&a\notin
A\end{array}\right.$

is proved to be a fuzzy subsemigroup of $S$. The above notions and other ones
that are needed to understand the rest of the paper can be found mostly in the
monograph [7]. Necessary concepts from semigroup theory are found in [3] and
[12]. From [12], we are presenting below theorem 9.3 whose fuzzy counterpart
is proved partially in [7]. We prove here its fuzzy counterpart theorem 4.1,
including the part already proved in [7], not in a direct fashion as in [7],
but as an implication of theorem 9.3 after having established a 1-1
correspondence between fuzzy one sided ideals of a semigroup $S$ on the one
hand, and one sided ideals of $S\times[0,1]$ on the other hand. Theorem 9.3 of
[12] reads as follows.

###### Theorem 1.1

The following are equivalent.

  * (i)

$S$ is a regular semigroups.

  * (ii)

For every right ideal $R$ and every fuzzy left ideal $L$, we have $R\cap
L=RL$.

  * (iii)

For every right ideal $R$ and every left ideal $L$ of $S$, (a) $R^{2}=R$, (b)
$L^{2}=L$, (c) $RL$ is a quasi-ideal of $S$.

  * (iv)

The set of all quasi-ideals of $S$ forms a regular semigroup.

  * (v)

For every quasi ideal $Q$ of $S$, $QSQ=Q$.

The last section of this paper is devoted to the semilattice decomposition of
left regular semigroups whose left ideals are also right ideals. It is proved
in [11] that such semigroups have a nice decomposition into smaller and easier
to understand subsemigroups. More specifically we have from [11] the following
theorem.

###### Theorem 1.2

For a semigroup $(S,\cdot)$ the following conditions are equivalent:

  * (1)

$S$ is a semilattice of left simple semigroups.

  * (2)

$L_{1}\cap L_{2}=L_{1}L_{2}$ for every left ideals $L_{1}$ and $L_{2}$ of $S$.

  * (3)

The set of all left ideals of $S$ is a semilattice under the multiplication of
subsets.

  * (4)

$S$ is left regular and every left ideal of $S$ is two-sided.

There is also a version of this theorem in [7] (Theorem 4.1.3) where condition
(2), (3) and (4) are fuzzyfied by replacing the term left ideal (resp. ideal)
by fuzzy left ideal (resp. fuzzy ideal). We prove in our theorem 5.1 that
condition (1) can also be fuzzyfied. For this we have defined what a fuzzy
semilattice of left simple fuzzy subsemigroups is. In the same spirit with the
above we give a fuzzy version of Theorem 4.1.3 of [3] by characterizing
completely regular semigroups in terms of what are defined here to be fuzzy
semilattices of completely simple fuzzy subsemigroups.

##  2 A relationship between fuzzy subsemigroups and semigroups

Assume we are given a fuzzy subsemigroup $f:S\rightarrow[0,1]$ of a semigroup
$(S,\cdot)$. Besides the semigroup $(S,\cdot)$ we consider the semilattice
$([0,1],\wedge)$. We sometimes write $I$ instead of $[0,1]$ and let
$I^{\ast}=I\setminus\\{0\\}$. We can obviously regard $f$ as a prehomomorphism
from $(S,\cdot)$ to $([0,1],\wedge)$. With this data at hand, we define a
subsemigroup of the direct product semigroup $(S,\cdot)\times([0,1],\wedge)$
by letting

$\mathfrak{S}(S,f)=\\{(b,y)\in S\times[0,1]:f(b)\geq y\\}.$

This is indeed a subsemigroup of $S\times[0,1]$ since for every
$(a,x),(b,y)\in\mathfrak{S}(S,f)$ we have that $f(ab)\geq f(a)\wedge f(b)\geq
x\wedge y$, and then,

$(a,x)(b,y)=(ab,x\wedge y)\in\mathfrak{S}(S,f).$

The semigroup $\mathfrak{S}(S,f)$ satisfies the following three conditions

  * (i)

$\pi_{1}(\mathfrak{S}(S,f))=S$ where $\pi_{1}$ is the projection in the first
coordinate,

  * (ii)

for every $b\in S$,
$(b,\text{sup}\\{y\in[0,1]:(b,y)\in\mathfrak{S}(S,f)\\})\in\mathfrak{S}(S,f)$,
since $\text{sup}\\{y\in[0,1]:(b,y)\in\mathfrak{S}(S,f)\\}=f(b)$, and

  * (iii)

$(b,y)\in\mathfrak{S}(S,f)$ for every $y\leq f(b)$.

Conversely, every subsemigroup $\Sigma$ of the direct product $S\times[0,1]$
which satisfies the following three conditions

  * (s-i)

$\pi_{1}(\Sigma)=S$ where $\pi_{1}$ is the projection in the first coordinate,

  * (s-ii)

for every $b\in S$, $(b,\text{sup}\\{y\in[0,1]:(b,y)\in\Sigma\\})\in\Sigma$,
and

  * (s-iii)

$(b,y)\in\Sigma$ for every $y\leq\text{sup}\\{z\in[0,1]:(b,z)\in\Sigma\\}$,

gives rise to a fuzzy subsemigroup $f:S\rightarrow[0,1]$ such that
$\mathfrak{S}(S,f)=\Sigma$. For this we define

$f:S\rightarrow[0,1]\text{ by
}b\mapsto\text{sup}\\{y\in[0,1]:(b,y)\in\Sigma\\}.$

From condition (ii) we know that $(b,f(b))\in\Sigma$. The function $f$ is a
fuzzy subsemigroup for if $a,b\in S$, then since $(a,f(a)),(b,f(b))\in\Sigma$,
it follows that

$(ab,f(a)\wedge f(b))=(a,f(a))(b,f(b))\in\Sigma,$

and then $f(ab)\geq f(a)\wedge f(b)$. Finally,

$\displaystyle(b,y)\in\mathfrak{S}(S,f)$ $\displaystyle\Leftrightarrow
f(b)\geq y$ $\displaystyle\Leftrightarrow(b,y)\in\Sigma$ (from condition
(s-iii))

The set of subsemigroups $\Sigma$ of $S\times I$ as above is denoted here by
$F(S\times I)$. Also we write $\mathfrak{F}(S)$ for the set of all fuzzy
subsemigroups of $S$. Define now

$\Psi:\mathfrak{F}(S)\rightarrow F(S\times I)\text{ by
}f\mapsto\mathfrak{S}(S,f).$

###### Proposition 2.1

The map $\Psi$ is bijective.

###### Proof.

That $\Psi$ is correct and onto was proved above. To prove that $\Psi$ is
injective, we let $f,g\in\mathfrak{F}(S)$ such that
$\mathfrak{S}(S,f)=\mathfrak{S}(S,g)$. Then, for every $a\in S$,
$(a,g(a))\in\mathfrak{S}(S,g)$, hence $(a,g(a))\in\mathfrak{S}(S,f)$, and then
$g(a)\leq f(a)$. In a symmetric way one can show that $f(a)\leq g(a)$,
therefore $g(a)=f(a)$. ∎

We conclude this section with a further remark on the relationships between
subsemigroups of $S\times I$ and fuzzy subsemigroups of $S$. Once we
associated every fuzzy subsemigroup of $S$ with a subsemigroup of $S\times I$,
we would like to establish a reverse correspondence. It is obvious that not
every subsemigroup of $S\times I$ is in the image of $\Psi$. For instance, if
$t\in I^{\ast}$ is fixed, then every subsemigroup $\Sigma$ of $S\times I$ with
$\pi_{2}(\Sigma)=t$ cannot be in the image of $\Psi$. But still we can define
a fuzzy subsemigroup $\sigma$ in terms of $\Sigma$ and find a relationship
between $\mathfrak{S}(S,\sigma)$ and $\Sigma$. For this we define
$\sigma:S\rightarrow I$ such that

$\sigma(a)=\left\\{\begin{array}[]{ccc}\alpha&if&a\in\pi_{1}(\Sigma)\\\
0&if&a\notin\pi_{1}(\Sigma),\end{array}\right.$

where $\alpha=\text{sup}\\{t\in I:(a,t)\in\Sigma\\}$. We prove that $\sigma$
is a fuzzy subsemigroup of $S$. Indeed, let $a,b\in S$. If
$ab\notin\pi_{1}(\Sigma)$, then it is obvious that at least one of $a$ or $b$
cannot be in $\pi_{1}(\Sigma)$, consequently
$\sigma(ab)=0=\sigma(a)\wedge\sigma(b)$. If $ab\in\pi_{1}(\Sigma)$ we let
$\gamma=\text{sup}C$ where $C=\text{sup}\\{t\in I:(ab,t)\in\Sigma\\}$. If now
$a,b\in\pi_{1}(\Sigma)$, we write $A=\\{t^{\prime}\in
I:(a,t^{\prime})\in\Sigma\\}$, $B=\\{t^{\prime\prime}\in
I:(b,t^{\prime\prime})\in\Sigma\\}$, and let $\alpha=\text{sup}A$ and
$\beta=\text{sup}B$. We prove that $\alpha\wedge\beta\leq\gamma$ which in turn
is equivalent to $\sigma(ab)\geq\sigma(a)\wedge\sigma(b)$. Observe first that
$t^{\prime}\wedge t^{\prime\prime}\in C$ for every $t^{\prime}\in A$ and
$t^{\prime\prime}\in B$ since $(ab,t^{\prime}\wedge
t^{\prime\prime})=(a,t^{\prime})(b,t^{\prime\prime})\in\Sigma$. Let us assume
that $\alpha<\beta$ or equivalently that $\alpha\wedge\beta=\alpha$. In this
case, there is $t_{\ast}^{\prime\prime}\in B$ such that
$t_{\ast}^{\prime\prime}>\alpha$, and then

$\displaystyle\alpha$ $\displaystyle=\text{sup}A$
$\displaystyle=\text{sup}\\{t^{\prime}\wedge
t_{\ast}^{\prime\prime}:t^{\prime}\in A\\}$
$\displaystyle\leq\text{sup}\\{t^{\prime}\wedge t^{\prime\prime}:t^{\prime}\in
A,t^{\prime\prime}\in B\\}$ $\displaystyle\leq\text{sup}C$ (from our
observation) $\displaystyle=\gamma.$

A similar proof is available when $\alpha>\beta$. Let us now prove the claim
when $\alpha=\beta$. There are increasing sequences
$\\{t^{\prime}_{n}\\}\subseteq A$ and $\\{t^{\prime\prime}_{n}\\}\subseteq B$
such that $t^{\prime}_{n}\rightarrow\alpha$ and
$t^{\prime\prime}_{n}\rightarrow\alpha$. It follows that $t^{\prime}_{n}\wedge
t^{\prime\prime}_{n}\rightarrow\alpha$, and then

$\displaystyle\alpha$ $\displaystyle=\text{sup}A$
$\displaystyle=\text{sup}\\{t^{\prime}_{n}:n\in\mathbb{N}\\}$
$\displaystyle=\text{sup}\\{t^{\prime}_{n}\wedge
t^{\prime\prime}_{n}:n\in\mathbb{N}\\}$ $\displaystyle\leq\text{sup}C$ (from
the obsevation) $\displaystyle=\gamma.$

In the three remaining cases when at least one of $a$ or $b$ is not in
$\pi_{1}(\Sigma)$ it is straightforward that $\alpha\wedge\beta\leq\gamma$.
Now we prove that $\Sigma\subseteq\mathfrak{S}(S,\sigma)$. Indeed, let
$(a,t)\in\Sigma$, then from the definition of $\sigma$, $\sigma(a)\geq t$,
hence $(a,t)\in\mathfrak{S}(S,\sigma)$. Letting $\text{Sub}(S\times I)$ be the
set of subsemigroups of the product semigroup $S\times I$, we define

$\tilde{\Psi}:\text{Sub}(S\times I)\rightarrow\mathfrak{F}(S)\text{ by
}\Sigma\mapsto\sigma,$

with $\sigma$ described as above. This map is obviously surjecive, and in
general non injective since if $\sigma$ is such that
$\Sigma\neq\mathfrak{S}(S,\sigma)$, then
$\tilde{\Psi}(\Sigma)=\sigma=\tilde{\Psi}(\mathfrak{S}(S,\sigma))$. The right
hand side equality above shows that $\tilde{\Psi}$ is a left inverse of
$\Psi$.

##  3 Similar relationships for other fuzzy subsystems

Given a fuzzy left ideal $f:S\rightarrow[0,1]$ of a semigroup $(S,\cdot)$, we
define a left ideal in the direct product semigroup $S\times[0,1]$ by

$\mathcal{L}(S,f)=\\{(b,y)\in S\times[0,1]:f(b)\geq y\\}.$

This is indeed a left ideal of $S\times[0,1]$ for if $(a,x)\in S\times[0,1]$
and $(b,y)\in\mathcal{L}(S,f)$, then

$(a,x)(b,y)=(ab,x\wedge y)\in\mathcal{L}(S,f)$

since

$f(ab)\geq f(b)\geq x\wedge f(b)\geq x\wedge y.$

We also note that $\mathcal{L}(S,f)$ satisfies the following three conditions:

  * (i)

$\pi_{1}(\mathcal{L}(S,f))=S$ where $\pi_{1}$ is the projection in the first
coordinate,

  * (ii)

for every $b\in S$,
$(b,\text{sup}\\{y\in[0,1]:(b,y)\in\mathcal{L}(S,f)\\})\in\mathcal{L}(S,f)$,
since $\text{sup}\\{y\in[0,1]:(b,y)\in\mathcal{L}(S,f)\\}=f(b)$, and

  * (iii)

$(b,y)\in\mathcal{L}(S,f)$ for every $y\leq f(b)$.

Conversely, every left ideal $L$ of the direct product semigroup
$S\times[0,1]$ which satisfies the following three conditions

  * (l-i)

$\pi_{1}(L)=S$ where $\pi_{1}$ is the projection in the first coordinate,

  * (l-ii)

for every $b\in S$, $(b,\text{sup}\\{y\in[0,1]:(b,y)\in L\\})\in L$, and

  * (l-iii)

$(b,y)\in L$ for every $y\leq\text{sup}\\{z\in[0,1]:(b,z)\in L\\}$,

gives rise to a fuzzy left ideal of $S$. For this we define

$f:S\rightarrow[0,1]:b\mapsto\text{sup}\\{y\in[0,1]:(b,y)\in L\\}.$

In particular we have that $(b,f(b))\in L$. Now we show that for all $a,b\in
S$, $f(ab)\geq f(b)$. Since $L$ is a left ideal, then for $(a,1)\in
S\times[0,1]$ and $(b,f(b))\in L$, we have

$(a,1)(b,f(b))=(ab,f(b))\in L,$

hence from the definition of $f$, we have $f(ab)\geq f(b)$. Also we note that
the left ideal $\mathcal{L}(S,f)$ arising from the fuzzy left ideal $f$
defined in terms of $L$ is exactly the left ideal $L$ we started with, that is
$\mathcal{L}(S,f)=L$. Indeed,

$\displaystyle(b,y)\in\mathcal{L}(S,f)$ $\displaystyle\Leftrightarrow f(b)\geq
y$ $\displaystyle\Leftrightarrow(b,y)\in L$ (from condition (l-iii))

A similar result with proposition 2.1 holds true for fuzzy left ideals. We let
$L(S\times I)$ be the set of left ideals of $S\times I$ which satisfy
properties (l-i), (l-ii) and (l-iii) above. Also we write $\mathfrak{L}(S)$
for the set of all fuzzy left ideals of $S$.

###### Proposition 3.1

The restriction $\Psi|_{\mathfrak{L}(S)}$ of $\Psi$ on $\mathfrak{L}(S)$ is a
bijection between $\mathfrak{L}(S)$ and $L(S\times I)$.

###### Proof.

It is straightforward that for every fuzzy left ideal $f$,
$\mathcal{L}(S,f)=\Psi(f)$, hence
$\Psi|_{\mathfrak{L}(S)}:\mathfrak{L}(S)\rightarrow L(S\times I)$ is well
defined. On the other hand, every left ideal $L$ of $L(S\times I)$ is in the
image of $\Psi$, hence the restriction map is onto. Finally,
$\Psi|_{\mathfrak{L}(S)}$ is 1-1 as a restriction of a 1-1 map. ∎

We note by passing that similar results hold true for fuzzy right ideals too.
For instance, one can prove that if we let $\mathfrak{R}(S)$ be the set of
fuzzy right ideals of $S$, and $R(S\times I)$ the set of right ideals of
$S\times I$ which satisfy certain condition similar to those $(l-i,ii,iii)$,
then we have,

###### Proposition 3.2

The restriction $\Psi|_{\mathfrak{R}(S)}$ of $\Psi$ on $\mathfrak{R}(S)$ is a
bijection between $\mathfrak{R}(S)$ and $R(S\times I)$.

We conclude this section by proving that analogous results to the above hold
true for fuzzy quasi-ideals.

###### Lemma 3.1

Whenever $q$ is a fuzzy quasi-ideal and $a\in S$ has a family of
factorizations $a=b_{i}c_{i}$ with $i\in J$, then $\forall i\in J$, $q(a)\geq
q(b_{i})$ or $q(a)\geq q(c_{i})$.

###### Proof.

From the definition of a fuzzy quasi-ideal $q$ we have

$\displaystyle q(a)$ $\displaystyle\geq(\underset{i\in
J}{\vee}q(b_{i}))\wedge(\underset{j\in J}{\vee}q(c_{j}))$
$\displaystyle=\underset{i\in J}{\vee}q(b_{i})$ (if for instance,)

then $q(a)\geq q(b_{i})$ for all $i\in J$. Similarly, one can show that when

$\text{min}\left(\underset{i\in J}{\vee}q(b_{i}),\underset{j\in
J}{\vee}q(c_{j})\right)=\underset{j\in J}{\vee}q(c_{j}),$

then $q(a)\geq q(c_{j})$. ∎

For every fixed fuzzy quasi-ideal $q$ of $S$, we let

$\mathfrak{Q}(S,q)=\\{(a,x)\in S\times I:q(a)\geq x\\},$

and prove that $\mathfrak{Q}(S,q)$ is a quasi-ideal of $S\times I$. Indeed, if
$(a,x),(b,y)\in\mathfrak{Q}(S,q)$ and $(s,t),(s^{\prime},t^{\prime})\in
S\times I$ are such that

$(a,x)(s,t)=(s^{\prime},t^{\prime})(b,y)\in\mathfrak{Q}(S,q)\cdot(S\times
I)\cap(S\times I)\cdot\mathfrak{Q}(S,q),$

then

$\displaystyle(as,x\wedge t)=(s^{\prime}b,t^{\prime}\wedge y),$

hence $as=s^{\prime}b$ and $q(as)=q(s^{\prime}b)$. From Lemma 3.1 we have that
either $q(as)\geq q(a)$, or $q(s^{\prime}b)\geq q(b)$. In the first case we
have that

$q(as)\geq q(a)\geq x\geq x\wedge t,$

which proves that $(a,x)(s,t)=(as,x\wedge t)\in\mathfrak{Q}(S,q)$. If the
second case above occurs, then

$q(s^{\prime}b)\geq q(b)\geq y\geq y\wedge t^{\prime},$

consequently, $(s^{\prime},t^{\prime})(b,y)=(s^{\prime}b,t^{\prime}\wedge
b)\in\mathfrak{Q}(S,q)$. We have thus proved that $\mathfrak{Q}(S,q)$ is a
quasi-ideal of $S\times I$. The quasi-ideal $\mathfrak{Q}(S,q)$ satisfies the
following properties

  * (i)

$\pi_{1}(\mathfrak{Q}(S,q))=S$ where $\pi_{1}$ is the projection in the first
coordinate,

  * (ii)

for every $b\in S$,
$(b,\text{sup}\\{y\in[0,1]:(b,y)\in\mathfrak{Q}(S,q)\\})\in\mathfrak{Q}(S,q)$,

  * (iii)

$(b,y)\in\mathfrak{Q}(S,q)$ for every
$y\leq\text{sup}\\{z\in[0,1]:(b,z)\in\mathfrak{Q}(S,q)\\}$, and

  * (iv)

if $a\in S$ has a family of decompositions $a=b_{i}c_{i}$ with $i\in J$, then
for all $i\in J$,

$\text{sup}\\{x\in[0,1]:(a,x)\in\mathfrak{Q}(S,q)\\}\geq\text{sup}\\{y\in[0,1]:(b_{i},y)\in\mathfrak{Q}(S,q)\\},$

or for all $i\in J$,

$\text{sup}\\{x\in[0,1]:(a,x)\in\mathfrak{Q}(S,q)\\}\geq\text{sup}\\{z\in[0,1]:(c_{i},z)\in\mathfrak{Q}(S,q)\\}.$

Conversely, every quasi-ideal $Q$ of the direct product semigroup
$S\times[0,1]$ which satisfies the following four conditions

  * (q-i)

$\pi_{1}(Q)=S$ where $\pi_{1}$ is the projection in the first coordinate,

  * (q-ii)

for every $b\in S$, $(b,\text{sup}\\{y\in[0,1]:(b,y)\in Q\\})\in Q$,

  * (q-iii)

$(b,y)\in Q$ for every $y\leq\text{sup}\\{z\in[0,1]:(b,z)\in Q\\}$, and

  * (q-iv)

If $a\in S$ has a family of decompositions $a=b_{i}c_{i}$ with $i\in J$, then
for all $i\in J$,

$\text{sup}\\{x\in[0,1]:(a,x)\in Q\\}\geq\text{sup}\\{y\in[0,1]:(b_{i},y)\in
Q\\},$

or for all $i\in J$,

$\text{sup}\\{x\in[0,1]:(a,x)\in Q\\}\geq\text{sup}\\{z\in[0,1]:(c_{i},z)\in
Q\\},$

gives rise to a fuzzy quasi ideal of $S$. Indeed, let $q:S\rightarrow[0,1]$ be
such that

$q(b)=\text{sup}\\{y\in[0,1]:(b,y)\in Q\\}.$

In particular we have that $(b,q(b))\in Q$. Now we show that $q\circ S\cap
S\circ q\subseteq q$. Let $a\in S$ be any fixed element. Denote by $J$ the set
of indexes for which there are $b_{i},c_{i}\in S$ with $i\in J$ such that
$a=b_{i}c_{i}$. To prove the above inclusion we need to prove that

$\underset{i\in J}{\vee}q(b_{i})\wedge\underset{j\in J}{\vee}q(c_{j})\leq
q(a),$

which due to the condition (q-iii) follows directly if we prove that

$(a,\underset{(i,j)\in I\times I}{\vee}q(b_{i})\wedge
q(c_{j}))=(a,\underset{i\in I}{\vee}q(b_{i})\wedge\underset{j\in
I}{\vee}q(c_{j}))\in Q.$

From condition (q-iv) we may assume that for instance $q(a)\geq q(b_{i})$ for
all $i\in J$, hence for each $j\in J$, we have from condition (q-iii) that
$(a,q(b_{i})\wedge q(c_{j}))\in Q$. Conditions (q-ii) and (q-iii) now imply
that $(a,\underset{(i,j)\in J\times J}{\vee}(q(b_{i})\wedge q(c_{i})))\in Q$,
and we are done. A similar proof is available if we assume that for all $j\in
J$, $q(a)\geq q(c_{j})$. Now we show that $\mathfrak{Q}(S,q)=Q$ for the fuzzy
quasi-ideal $q$ defined in terms of the given $Q$. Indeed,

$\displaystyle(b,y)\in\mathfrak{Q}(S,q)$ $\displaystyle\Leftrightarrow
q(b)\geq y$ $\displaystyle\Leftrightarrow(b,y)\in Q$ (from (q-iii)).

In a similar fashion with the case of fuzzy left and right ideals, we denote
here by $Q(S\times I)$ the set of all quasi-ideals of $S\times I$ that satisfy
conditions (q i-iv), and let $\mathfrak{Q}(S)$ be the set of all fuzzy quasi-
ideals of $S$. With these notations we have this

###### Proposition 3.3

The restriction $\Psi|_{\mathfrak{Q}(S)}$ of $\Psi$ on $\mathfrak{Q}(S)$ is a
bijection between $\mathfrak{Q}(S)$ and $Q(S\times I)$.

###### Proof.

The map $\Psi$ sends $q\mapsto\mathfrak{Q}(S,q)\in Q(S\times I)$ and this map
is onto from the above. The injectivity of $\Psi|_{\mathfrak{Q}(S)}$ is dealt
with in the same way as that of fuzzy one sided ideals. ∎

##  4 Regular Semigroups

Our next Theorem 4.1 is the fuzzy analogue of theorem 9.3 of [12] and is
partially covert from theorems 3.1.2-3.1.8 of [7] apart from characterization
(iv) which is a new fuzzyfication of its counterpart in theorem 9.3 of [12].
This theorem characterizes the regularity of a semigroup in terms of fuzzy one
sided ideals and fuzzy quasi-ideals but in contrast with [7] where the proofs
are analogue to those of theorem 9.3 of [12], our proofs employ the
identifications of Proposition 3.1 and Proposition 3.2, to obtain the result
as an implication of the corresponding result of theorem 9.3 of [12]. The
following lemma will be useful in the proof of theorem 4.1.

###### Lemma 4.1

Let $B,C$ be subsemigroups of a semigroup $S$, and let $\chi_{B}$ and
$\chi_{C}$ be the corresponding fuzzy subsemigroups. Then,
$\chi_{B}\circ\chi_{C}=\chi_{BC}$.

###### Proof.

For every $a\in S$ we have that,

$\displaystyle(\chi_{B}\circ\chi_{C})(a)=1$
$\displaystyle\Leftrightarrow\underset{a=st}{\vee}\chi_{B}(s)\wedge\chi_{C}(t)=1$
$\displaystyle\Leftrightarrow\text{ there is a decomposition }a=st,\text{ with
}\chi_{B}(s)=1\text{ and }\chi_{C}(t)=1$ $\displaystyle\Leftrightarrow\text{
there is a decomposition }a=st,\text{ with }s\in B\text{ and }t\in C$
$\displaystyle\Leftrightarrow a\in BC$
$\displaystyle\Leftrightarrow\chi_{BC}(a)=1.$

Further, if $(\chi_{B}\circ\chi_{C})(a)=0$, then either $a$ does not have a
nontrivial decomposition $a=st$, in which case $a\notin BC$ and then
$\chi_{BC}(a)=0$, or $a$ decomposes as $a=st$ but for every such decomposition
we should have that $\chi_{B}(s)\wedge\chi_{C}(t)=0$. This means that either
$s\notin B$ or $t\notin C$, consequently $a\notin BC$ and $\chi_{BC}(a)=0$.
Conversely, if $\chi_{BC}(a)=0$, then, either $a$ is indecomposable, or even
it is, it can never be written as $a=st$ with both $s\in B$ and $t\in C$,
consequently $(\chi_{B}\circ\chi_{C})(a)=0$. Recollecting we have that
$\chi_{B}\circ\chi_{C}=\chi_{BC}$. ∎

###### Theorem 4.1

The following are equivalent.

  * (i)

$S$ is a regular semigroups.

  * (ii)

For every fuzzy right ideal $f$ and every fuzzy left ideal $g$, we have $f\cap
g=f\circ g$.

  * (iii)

For every fuzzy right ideal $f$ and every fuzzy left ideal $g$ of $S$, (a)
$f\circ f=f$, (b) $g\circ g=g$, (c) $f\circ g$ is a fuzzy quasi-ideal of $S$.

  * (iv)

The set $\mathcal{Q}(S)$ of all fuzzy quasi-ideals of $S$ forms a regular
semigroup where the multiplication is $\circ$ and for every
$q\in\mathcal{Q}(S)$, $q\circ S\circ q=q$..

###### Proof.

$(i)\Rightarrow(ii)$: The regularity of $S$ implies that of $S\times I$.
Indeed, for every $(a,x)\in S\times I$, let $a^{\prime}\in S$ such that
$aa^{\prime}a=a$. Then, $(a,x)(a^{\prime},x)(a,x)=(a,x)$ proving that $(a,x)$
has an inverse. Being regular for $S\times I$ means that for every right ideal
$R$ and every left ideal $L$ of $S\times I$, we have that $R\cap L=RL$. We can
apply this by taking $R=\mathfrak{R}(S,f)=\Psi(f)$ the fuzzy right ideal of
$S$ associated with an arbitrary fuzzy right ideal $f$, and
$L=\mathfrak{L}(S,g)=\Psi(g)$ the fuzzy left ideal of $S$ associated with an
arbitrary fuzzy left ideal $g$. In this particular case we have
$\mathfrak{R}(S,f)\cap\mathfrak{L}(S,g)=\mathfrak{R}(S,f)\mathfrak{L}(S,g)$.
Further, for every $a\in S$, we assume that $(f\cap g)(a)=f(a)$ which means
that $f(a)=\text{min}(f(a),g(a))$. Under this assumption we will prove that

$(f\cap g)(a)=f(a)=\vee_{a=bc}(f(b)\wedge g(c))=(f\circ g)(a).$

A similar proof can be provided in case $g(a)=\text{min}(f(a),g(a))$. Since
$f(a)\leq g(a)$, then $(a,f(a))\in\mathfrak{R}(S,f)\cap\mathfrak{L}(S,g)$ and
$(a,f(a))\in\mathfrak{R}(S,f)\mathfrak{L}(S,g)$. Hence, there are
$(b,x)\in\mathfrak{R}(S,f)$ and $(c,y)\in\mathfrak{L}(S,g)$ such that
$(a,f(a))=(b,x)(c,y)$. It follows that $a=bc$, and that

$f(a)=x\wedge y\leq f(b)\wedge g(c).$

But $f$ is a fuzzy right ideal, then $f(b)\leq f(bc)=f(a)$, hence

$f(b)\leq f(a)\leq f(b)\wedge g(c)\leq f(b),$

which implies that $f(a)=f(b)=f(b)\wedge g(c)$. Now we write $(f\circ g)(a)$
as

$(f\circ g)(a)=(f(b)\wedge
g(c))\vee(\vee_{a=b^{\prime}c^{\prime},b^{\prime}\neq b}(f(b^{\prime})\wedge
g(c^{\prime}))),$

and obtain from the above that

$(f\circ g)(a)=f(a)\vee(\vee_{a=b^{\prime}c^{\prime},b^{\prime}\neq
b}(f(b^{\prime})\wedge g(c^{\prime})))\geq f(a).$

But on the other hand we have that

$\displaystyle(f\circ
g)(a)=\vee_{a=b^{\prime\prime}c^{\prime\prime}}(f(b^{\prime\prime})\wedge
g(c^{\prime\prime}))$
$\displaystyle\leq\vee_{a=b^{\prime\prime}c^{\prime\prime}}f(b^{\prime\prime})$
$\displaystyle\leq f(b^{\prime\prime}c^{\prime\prime})$ (since $f$ is a fuzzy
right ideal) $\displaystyle=f(a).$

Therefore we finally have that $(f\circ g)(a)=f(a)=(f\cap g)(a)$.
$(ii)\Rightarrow(i)$: Let $R$ and $L$ be arbitrary right and left ideals of
$S$ and $\chi_{R}$ and $\chi_{L}$ be their respective fuzzy right and left
ideals. From the assumption we have that
$\chi_{R}\cap\chi_{L}=\chi_{R}\circ\chi_{L}$. On the one hand, it is obvious
that $\chi_{R}\cap\chi_{L}=\chi_{R\cap L}$, and on the other hand we have from
lemma 4.1 that $\chi_{R}\circ\chi_{L}=\chi_{RL}$. Combining both equalities we
derive that $R\cap L=RL$. Now theorem 9.3 [12] implies (i).
$(i)\Rightarrow(iii)$: Let $f$ be a fuzzy right ideal of $S$ and let
$\mathfrak{R}(f,S)=\Psi(f)$ be the respective right ideal of $S\times I$.
Since $S$ is regular, so is $S\times I$ and then (iii) of theorem 9.3 [12]
implies that $\mathfrak{R}(f,S)\mathfrak{R}(f,S)=\mathfrak{R}(f,S)$. We imply
from this that $f\circ f=f$. For every $a\in S$,
$(a,f(a))\in\mathfrak{R}(f,S)$, hence there are
$(b,y),(c,z)\in\mathfrak{R}(f,S)$ such that

$(a,f(a))=(b,y)(c,z)=(bc,y\wedge z).$

In particular we have that $a$ has a decomposition $a=bc$ and that

$f(a)=y\wedge z\leq f(b)\wedge f(c).$

It follows from this that

$(f\circ f)(a)=(f(b)\wedge
f(c))\vee\left(\underset{\underset{(b^{\prime},c^{\prime})\neq(b,c)}{a=b^{\prime}c^{\prime}}}{\vee}f(b^{\prime})\wedge
f(c^{\prime})\right)\geq f(a).$

On the other hand we have that

$\displaystyle(f\circ f)(a)$
$\displaystyle=\underset{a=b^{\prime}c^{\prime}}{\vee}f(b^{\prime})\wedge
f(c^{\prime})$
$\displaystyle\leq\underset{a=b^{\prime}c^{\prime}}{\vee}f(a)\wedge
f(c^{\prime})$ (since $f$ is a fuzzy right ideal) $\displaystyle\leq f(a).$

Combining both inequalities we obtain that $(f\circ f)(a)=f(a)$.
In a similar fashion one can prove that for every fuzzy left ideal $g$ we have
that $g\circ g=g$. Finally, that $f\circ g$ is a fuzzy quasi-ideal of $S$ for
every fuzzy right ideal $f$ and every fuzzy left ideal $g$, follows from Lemma
2.6.5 [7] and from the equality $f\circ g=f\cap g$ which is a consequence of
the equivalence $(i)\Leftrightarrow(ii)$.
$(iii)\Rightarrow(i)$: Under the assumptions that for every fuzzy right ideal
$f$ and every fuzzy left ideal $g$, we have that $f\circ f=f$, $g\circ g=g$
and $f\circ g$ is a fuzzy quasi-ideal, we prove that for every right ideal $R$
of $S$ and every left ideal $L$ of $S$ we have that $RR=R$, $LL=L$ and that
$RL$ is a quasi-ideal of $S$. These three conditions imply from theorem 9.3 of
[12] that $S$ is regular. Consider now the fuzzy right ideal $\chi_{R}$ and
the fuzzy left ideal $\chi_{L}$ for which we have that
$\chi_{R}\circ\chi_{R}=\chi_{R}$, $\chi_{L}\circ\chi_{L}=\chi_{L}$ and that
$\chi_{R}\circ\chi_{L}$ is a fuzzy quasi-ideal of $S$. Lemma 4.1 and the first
two assumptions imply immediately that $RR=R$ and $LL=L$. Again lemma 4.1
implies that $\chi_{R}\circ\chi_{L}=\chi_{RL}$, which from our assumption is a
fuzzy quasi-ideal of $S$. Then lemma 2.6.4 of [7] implies $RL$ is a quasi-
ideal of $S$.
$(i)\Rightarrow(iv)$: Let $q_{1},q_{2}\in\mathcal{Q}(S)$ be arbitrary and
$\mathfrak{Q}(q_{1},S)$, $\mathfrak{Q}(q_{2},S)$ be their corresponding quasi
ideals of $S\times I$. We know from theorem 9.3 [12] that
$\mathfrak{Q}(q_{1},S)\mathfrak{Q}(q_{2},S)$ is a quasi-ideal of $S\times I$
since $S\times I$ is regular. Let $a\in S$ be arbitrary and want to show that

$((q_{1}\circ q_{2})\circ S\wedge S\circ(q_{1}\circ q_{2}))(a)\leq(q_{1}\circ
q_{2})(a).$

Assume now that $a$ decomposes as $a=b_{i}c_{i}d_{i}$ where $i\in J$, so the
above inequality now writes as

$\underset{i\in J}{\vee}(q_{1}(b_{i})\wedge q_{2}(c_{i}))\wedge\underset{i\in
J}{\vee}(q_{1}(c_{i})\wedge q_{2}(d_{i}))\leq(q_{1}\circ q_{2})(a),$

which is equivalent to

$\underset{(i,j)\in J\times J}{\vee}(q_{1}(b_{i})\wedge q_{2}(c_{i})\wedge
q_{1}(c_{j})\wedge q_{2}(d_{j}))\leq(q_{1}\circ q_{2})(a).$

This follows if we prove that for every $(i,j)\in J\times J$ we have

$q_{1}(b_{i})\wedge q_{2}(c_{i})\wedge q_{1}(c_{j})\wedge
q_{2}(d_{j})\leq(q_{1}\circ q_{2})(a).$ (1)

For this consider the element $(a,q_{1}(b_{i})\wedge q_{2}(c_{i})\wedge
q_{1}(c_{j})\wedge q_{2}(d_{j}))\in S\times I$ for which we have

$\displaystyle\mathfrak{Q}(q_{1},S)\mathfrak{Q}(q_{2},S)(S\times I)$
$\displaystyle\ni(b_{i},q_{1}(b_{i}))(c_{i},q_{2}(c_{i}))(d_{i},q_{1}(c_{j})\wedge
q_{2}(d_{j}))$ $\displaystyle=(a,q_{1}(b_{i})\wedge q_{2}(c_{i})\wedge
q_{1}(c_{j})\wedge q_{2}(d_{j}))$ $\displaystyle=(b_{j},q_{1}(b_{i})\wedge
q_{2}(c_{i}))(c_{j},q_{1}(c_{j}))(d_{j},q_{2}(d_{j}))$
$\displaystyle\in(S\times I)\mathfrak{Q}(q_{1},S)\mathfrak{Q}(q_{2},S).$

Since $\mathfrak{Q}(q_{1},S)\mathfrak{Q}(q_{2},S)(S\times I)\cap(S\times
I)\mathfrak{Q}(q_{1},S)\mathfrak{Q}(q_{2},S)\subseteq\mathfrak{Q}(q_{1},S)\mathfrak{Q}(q_{2},S)$,
then

$(a,q_{1}(b_{i})\wedge q_{2}(c_{i})\wedge q_{1}(c_{j})\wedge
q_{2}(d_{j}))\in\mathfrak{Q}(q_{1},S)\mathfrak{Q}(q_{2},S),$

therefore there are $(s,x)\in\mathfrak{Q}(q_{1},S)$ and
$(t,y)\in\mathfrak{Q}(q_{2},S)$ such that

$(a,q_{1}(b_{i})\wedge q_{2}(c_{i})\wedge q_{1}(c_{j})\wedge
q_{2}(d_{j}))=(s,x)(t,y)=(st,x\wedge y).$ (2)

It follows that

$\displaystyle(q_{1}\circ q_{2})(a)$ $\displaystyle=(q_{1}\circ q_{2})(st)$
(since $a=st$) $\displaystyle\geq q_{1}(s)\wedge q_{2}(t)$ (from the
definition of $\circ$) $\displaystyle\geq x\wedge y$ (since $q_{1}(s)\geq x$
and $q_{2}(t)\geq y$) $\displaystyle=q_{1}(b_{i})\wedge q_{2}(c_{i})\wedge
q_{1}(c_{j})\wedge q_{2}(d_{j})$ (from (2)).

This proves (1) and we are done with the first part of the proof. It remains
to prove that $(\mathcal{Q}(S),\circ)$ is regular. For this we utilize again
theorem 9.3 [12] where it is proved that for every quasi-ideal $Q$ of $S$ we
have that $QSQ=Q$. Let $q\in\mathcal{Q}(S)$ and $\mathfrak{Q}(q,S)$ its
corresponding quasi-ideal of $S\times I$ which satisfies

$\mathfrak{Q}(q,S)(S\times I)\mathfrak{Q}(q,S)=\mathfrak{Q}(q,S).$

We use this and the obvious fact that $S\in\mathcal{Q}(S)$ to show that
$q\circ S\circ q=q$ which would prove that $q$ is regular. First we show that
for every $a\in S$, $(q\circ S\circ q)(a)\leq q(a)$. Indeed, since

$(q\circ S\circ q)(a)=\underset{a=bcd}{\vee}q(b)\wedge q(d),$

to prove the inequality, it is enough to show that $q(a)\geq q(b)$ or
$q(a)\geq q(d)$ for every decomposition $a=bcd$. But either one or the other
is insured from lemma 3.1 and then the result follows. Conversely,
$(a,q(a))\in\mathfrak{Q}(q,S)$, therefore there are
$(b,x),(d,y)\in\mathfrak{Q}(q,S)$ and $(c,z)\in S\times I$ such that

$(a,q(a))=(b,x)(c,z)(d,y)=(bcd,x\wedge z\wedge y).$

From this it follows that

$\displaystyle q(a)$ $\displaystyle=x\wedge z\wedge y$ $\displaystyle\leq
q(b)\wedge q(d)$ (since $x\leq q(b)$ and $y\leq q(d)$)
$\displaystyle\leq(q\circ S\circ q)(a)$ (since $a=bcd$,)

hence $q(a)\leq(q\circ S\circ q)(a)$ which concludes the proof.
$(iv)\Rightarrow(i)$: If we prove that for every quasi-ideal $Q$ of $S$ we
have that $QSQ=Q$, then Theorem 9.3 of [12] implies that $S$ is regular.
Consider $\chi_{Q}$ which from Lemma 2.6.4 of [7] is a fuzzy quasi-ideal of
$S$ for which we have that $\chi_{Q}=\chi_{Q}\circ\chi_{S}\circ\chi_{Q}$. From
Lemma 4.1 we can write the above as $\chi_{Q}=\chi_{QSQ}$ which implies that
$Q=QSQ$ and we are done. ∎

##  5 Semilattice decompositions

Recall from [11] that a semigroup $S$ is called left regular if for every
$a\in S$, there is $x\in S$ such that $a=xa^{2}$. Likewise regular semigroups,
left regular ones have the property that every element have nontrivial
decompositions as a product of two elements. Most importantly, as shown in
[11], the left regular semigroups whose every left ideal is two-sided,
decompose as semilattices of left simple semigroups. We will generalize this
by introducing here fuzzy semilattices of left simple fuzzy subsemigroups.
Before we give our next definition, we recall that for every fuzzy
subsemigroup $f$ of a given semigroup $S$ and every $t\in I$, there is the so
called level subset (or the $t$-cut) $f_{t}=\\{a\in S:f(a)\geq t\\}$
associated with $t$. It is obvious that $f_{t}$ is a subsemigroup of $S$.

###### Definition 5.1

Let $(Y,\cdot)$ be a semilattice and $f_{\alpha}$ for $\alpha\in Y$ be a
family of fuzzy subsemigroups of a semigroup $S$. We say that this family
forms a fuzzy semilattice of fuzzy subsemigroups of $S$ if the following three
conditions are satisfied.

  * (i)

$\forall a\in S$, and all $\alpha,\beta\in Y$ with $\alpha\neq\beta$, we have
that $f_{\alpha}(a)\wedge f_{\beta}(a)=0$.

  * (ii)

For all $\alpha,\beta\in Y$, $f_{\alpha}\circ f_{\beta}\subseteq
f_{\alpha\cdot\beta}$.

  * (iii)

$\forall(\alpha,t)\in Y\times I^{\ast}$, $(f_{\alpha})_{t}\neq\emptyset$, and
$\forall(a,t)\in S\times I^{\ast}$, $\exists\alpha\in Y$ such that
$a\in(f_{\alpha})_{t}$.

In such a case we say that $S$ is a fuzzy semilattice of fuzzy subsemigroups
of $S$. We observe the following.

###### Proposition 5.1

If a semigroup $S$ has a semilattice decomposition, then $S$ has a fuzzy
semilattice decomposition.

###### Proof.

Assume that $S$ is a semilattice of semigroups $S_{\alpha}$ with $\alpha\in Y$
where $Y$ is a semilattice. Let $\chi_{S_{\alpha}}$ be the corresponding fuzzy
subsemigroups of $S$. We show that the family $\chi_{S_{\alpha}}$ with
$\alpha\in Y$ forms a fuzzy semilattice of left simple fuzzy subsemigroups of
$S$. Let $\alpha\neq\beta$ be elements of $Y$ and $a\in S$ be arbitrary. If
$a\notin S_{\alpha}\cup S_{\beta}$, then
$\chi_{S_{\alpha}}(a)\wedge\chi_{S_{\beta}}(a)=0$. If $a\in S_{\alpha}$, then
$\chi_{S_{\alpha}}(a)\wedge\chi_{S_{\beta}}(a)=0$, and similarly, if $a\in
S_{\beta}$, then $\chi_{S_{\alpha}}(a)\wedge\chi_{S_{\beta}}(a)=0$. Secondly,
for all $\alpha,\beta\in Y$, we have that

$\displaystyle\chi_{S_{\alpha}}\circ\chi_{S_{\beta}}$
$\displaystyle=\chi_{S_{\alpha}S_{\beta}}$ (from Lemma 4.1)
$\displaystyle\subseteq\chi_{S_{\alpha\cdot\beta}}$ (since
$S_{\alpha}S_{\beta}\subseteq S_{\alpha\cdot\beta}$).

Thirdly, $\forall(\alpha,t)\in Y\times I^{\ast}$,
$(\chi_{S_{\alpha}})_{t}\neq\emptyset$ since for $t\neq 0$,
$(\chi_{S_{\alpha}})_{t}=S_{\alpha}$. Also $\forall(a,t)\in S\times I^{\ast}$,
$\exists\alpha\in Y$ such that $a\in(\chi_{S_{\alpha}})_{t}$. We can chose
$\alpha\in Y$ such that $a\in S_{\alpha}$, and then $a\in
S_{\alpha}=(\chi_{S_{\alpha}})_{t}$. ∎

###### Proposition 5.2

If $S$ is a fuzzy semilattice of fuzzy subsemigroups of $S$, then $S\times
I^{\ast}$ has a semilattice decomposition.

###### Proof.

Assume that $S$ is a fuzzy semilattice of fuzzy subsemigroups $f_{\alpha}$
with $\alpha\in Y$. We define for each $\alpha\in Y$ the set

$\mathfrak{S}^{\ast}(f_{\alpha},S)=\\{(a,t)\in S\times
I^{\ast}:f_{\alpha}(a)\geq t\\}.$

This set is nonempty from the assumption (iii) on $f_{\alpha}$, and clearly
forms a subsemigroup of $S\times I^{\ast}$. For every fixed pair
$(\alpha,t)\in Y\times I^{\ast}$ we consider the nonempty set

$(f_{\alpha})_{t}=\\{a\in S:f_{\alpha}(a)\geq t\\}=\\{a\in
S:(a,t)\in\mathfrak{S}^{\ast}(f_{\alpha},S)\\},$

and let

$f_{(\alpha,t)}=(f_{\alpha})_{t}\times\\{t\\}.$

It is straightforward that $f_{(\alpha,t)}$ is a subsemigroup of $S\times
I^{\ast}$. We will prove that the family of all $f_{(\alpha,t)}$ forms a
semilattice decomposition of subsemigroups for $S\times I^{\ast}$, where the
index semilattice is $(Y,\cdot)\times(I^{\ast},\wedge)$. We observe that for
each $\alpha\in Y$,

$\mathfrak{S}^{\ast}(f_{\alpha},S)=\underset{t\in
I^{\ast}}{\cup}f_{(\alpha,t)}.$ (3)

With this observation in mind we prove that the family of all $f_{(\alpha,t)}$
with $(\alpha,t)\in Y\times I^{\ast}$, are pairwise disjoint. Indeed, for
every fixed $\alpha\in Y$, two different
$f_{(\alpha,t)},f_{(\alpha,t^{\prime})}$ do not intersect since $t\neq
t^{\prime}$. To prove that for all $\alpha\neq\beta$ and $t,t^{\prime}\in
I^{\ast}$, $f_{(\alpha,t)}\cap f_{(\beta,t^{\prime})}=\emptyset$ it is enough
to prove that
$\mathfrak{S}^{\ast}(f_{\alpha},S)\cap\mathfrak{S}^{\ast}(f_{\beta},S)=\emptyset$.
Let for this
$(a,t)\in\mathfrak{S}^{\ast}(f_{\alpha},S)\cap\mathfrak{S}^{\ast}(f_{\beta},S)$,
then

$f_{\alpha}(a)\geq t\text{ and }f_{\beta}(a)\geq t,$

which is impossible since one of $f_{\alpha}(a)$ or $f_{\beta}(a)$ has to be
zero from definition 5.1, (i). So it remains that
$\mathfrak{S}^{\ast}(f_{\alpha},S)\cap\mathfrak{S}^{\ast}(f_{\beta},S)=\emptyset$.
Let us prove that for every $(\alpha,t),(\beta,t^{\prime})\in Y\times
I^{\ast}$ we have that $f_{(\alpha,t)}f_{(\beta,t^{\prime})}\subseteq
f_{(\alpha\cdot\beta,t\wedge t^{\prime})}$. Indeed, for every $(a,t)\in
f_{(\alpha,t)}$ and $(b,t^{\prime})\in f_{(\beta,t^{\prime})}$ we have that

$\displaystyle f_{\alpha\cdot\beta}(ab)$ $\displaystyle\geq(f_{\alpha}\circ
f_{\beta})(ab)$ (from definition 5.1, (ii))
$\displaystyle=\underset{a^{\prime}b^{\prime}=ab}{\vee}f_{\alpha}(a^{\prime})\wedge
f_{\beta}(b^{\prime})$ $\displaystyle\geq f_{\alpha}(a)\wedge f_{\beta}(b)$
$\displaystyle\geq t\wedge t^{\prime},$

which implies that

$(a,t)(b,t^{\prime})=(ab,t\wedge t^{\prime})\in f_{(\alpha\cdot\beta,t\wedge
t^{\prime})}.$

Finally, that $\underset{(\alpha,t)\in Y\times
I^{\ast}}{\cup}f_{(\alpha,t)}=S\times I^{\ast}$ follows directly from
definition 5.1, (iii). ∎

###### Definition 5.2

A fuzzy subsemigroup $f$ of a semigroup $S$ is called a left simple fuzzy
subsemigroup of $S$ if for every $t\in I^{\ast}$, the set $f_{t}=\\{a\in
S:f(a)\geq t\\}$ is nonempty and forms a left simple subsemigroup of $S$.

This definition is consistent with the definition of a left simple
subsemigroup $A$ of $S$. Indeed, in that case the property of the fuzzy
subsemigroup $\chi_{A}$ that $(\chi_{A})_{t}=\\{a\in S:\chi_{A}(a)\geq t\\}$
is left simple for all $t\in I^{\ast}$ means exactly that $A$ is a left simple
subsemigroup of $S$ since for $t\in I^{\ast}$, $(\chi_{A})_{t}=A$.

###### Theorem 5.1

For a semigroup $(S,\cdot)$ the following conditions are equivalent:

  * (1’)

$S$ is a fuzzy semilattice of left simple fuzzy subsemigroups of $S$.

  * (1)

$S$ is a semilattice of left simple semigroups.

###### Proof.

We begin by proving that $(1^{\prime})\Rightarrow(1)$. Assumption (1’) and
Proposition 5.2 imply that there is a semilattice decomposition of $S\times
I^{\ast}$ with components $f_{(\alpha,t)}=(f_{\alpha})_{t}\times\\{t\\}$ where
$(\alpha,t)\in Y\times I^{\ast}$ and $Y$ is a semilattice. Further we show
that each $f_{(\alpha,t)}$ is a left simple subsemigroup of $S\times
I^{\ast}$. Indeed, since $f_{(\alpha,t)}=(f_{\alpha})_{t}\times\\{t\\}$ and

$(f_{\alpha})_{t}=\\{a\in
S:(a,t)\in\mathfrak{S}^{\ast}(f_{\alpha},S)\\}=\\{a\in S:f_{\alpha}(a)\geq
t\\},$

we have from our assumption and definition 5.2 that $f_{(\alpha,t)}$ is left
simple. Saito’s theorem now implies that $S\times I^{\ast}$ is left regular
and that every left ideal there is two sided. The first implies that $S$ is
also left regular, and the second implies that every left ideal of $S$ is two
sided. To see the second one, we let $L$ be a left ideal of $S$, and $t\in
I^{\ast}$, then clearly $L\times(0,t]$ is a left ideal of $S\times I^{\ast}$
and hence a right ideal. Let now $s\in S$ and $a\in L$ be arbitrary. Then for
every $(a,t^{\prime})\in L\times(0,t]$ and $(s,u)\in S\times I^{\ast}$ we have
that $(as,t^{\prime}\wedge u)=(a,t^{\prime})(s,u)\in L\times(0,t]$,
consequently $as\in L$ which proves that $L$ is a right ideal of $S$.

Let us now prove the converse implication $(1)\Rightarrow(1^{\prime})$. Assume
that $S$ is a semilattice of left simple semigroups $S_{\alpha}$ with
$\alpha\in Y$ where $Y$ is a semilattice. From Proposition 5.1, we have that
the family $\chi_{S_{\alpha}}$ with $\alpha\in Y$ forms a fuzzy semilattice of
fuzzy subsemigroups of $S$. In addition, each $\chi_{S_{\alpha}}$ is a left
simple fuzzy subsemigroup. This is obvious from the comment after definition
5.2. ∎

Theorem 4.1.3 of [3] states that Every completely regular semigroup is a
semilattice of completely simple semigroups. Our next attempt will be to
generalize this by replacing the semilattice of completely simple semigroups
with fuzzy semilattice of completely simple fuzzy subsemigroups. We make first
the following definition.

###### Definition 5.3

A fuzzy subsemigroup $f$ of a semigroup $S$ is called a completely simple
fuzzy subsemigroup of $S$ if for each $t\in I^{\ast}$, the set $f_{t}=\\{a\in
S:f(a)\geq t\\}$ is a nonempty and forms a completely simple subsemigroup of
$S$.

As in the case of left simple fuzzy subsemigroups, the above definition
generalizes completely simple subsemigroups of $S$, for if $A$ is such one,
then $\chi_{A}$ has the property that for each $t\in I^{\ast}$,
$(\chi_{A})_{t}=\\{a\in S:\chi_{A}(a)\geq t\\}=A$ is a completely simple
subsemigroup.

###### Theorem 5.2

Every completely regular semigroup $S$ is a fuzzy semilattice of completely
simple fuzzy subsemigroups.

###### Proof.

If we prove that $S$ being a fuzzy semilattice of completely simple fuzzy
subsemigroups is equivalent to $S$ being a semilattice of completely simple
subsemigroups, then our claim follows from Theorem 4.1.3 of [3]. Assume that
there is a semilattice $Y$ and a family $f_{\alpha}$ with $\alpha\in Y$, of
completely simple fuzzy subsemigroups of $S$ which form a fuzzy semilattice
decomposition for $S$. We first show that $S\times I^{\ast}$ has a semilattice
decomposition of completely simple subsemigroups. Indeed, from Proposition 5.2
we have that the family $f_{(\alpha,t)}=(f_{\alpha})_{t}\times\\{t\\}$ with
$(\alpha,t)\in Y\times I^{\ast}$ is a semilattice decomposition of $S\times
I^{\ast}$. Our assumption together with definition 5.3 imply that each
$f_{(\alpha,t)}$ is a completely simple subsemigroup of $S\times I^{\ast}$.
Secondly, Proposition 4.1.2 of [3] implies that each $f_{(\alpha,t)}$ is
completely regular. Thirdly, let $a\in S$ be arbitrary. For every $t\in
I^{\ast}$, from our assumption of the family $f_{\alpha}$, there is $\alpha\in
Y$ such that $(a,t)\in f_{(\alpha,t)}$. Since $f_{(\alpha,t)}$ is completely
regular, it follows that $(f_{\alpha})_{t}$ is completely regular as well,
therefore there is a subgroup of $(f_{\alpha})_{t}$ containing $a$. This
proves that $S$ is completely regular. Theorem 4.1.3 of [3] implies that $S$
is a semilattice of completely simple subsemigroups. For the converse, assume
that $S$ is a semilattice $Y$ of completely simple subsemigroups $S_{\alpha}$
with $\alpha\in Y$. Consider the family of fuzzy subsemigroups
$\chi_{S_{\alpha}}$ with $\alpha\in Y$. From Proposition 5.1 we have that this
family forms a fuzzy semilattice of fuzzy subsemigroups of $S$. The comment
after definition 5.3 implies that each $\chi_{S_{\alpha}}$ is fuzzy completely
simple. ∎

## References

  * [1] J. Ahsan, M.F. Khan, and M. Shabir, Characterization of monoids by the properties of their fuzzy subsystems, Fuzzy Sets and Systems, 56(1993),199-208.
  * [2] J. Ahsan, R.M. Latif, and M. Shabir, Fuzzy quasi-ideals in semigroups, J. Fuzzy Math., 9(2001) 259-270.
  * [3] J. M. Howie, Fundamentals of Semigroup Theory, Clarendon Press, Oxford, 1995
  * [4] N. Kuroki, On fuzzy semigroups, Inform. Sei., 53(1991) 203-236.
  * [5] N. Kuroki, Regular and intra-regular semigroups, Tokyo Gakugei J. Math. Edu., 3(1991) 51-54
  * [6] N. Kuroki, On fuzzy quasi-ideals in semigroups, Advances in Fuzzy Theory and Teehnology Vol. 1 (Ed. Paul P. Wang) Duke University, North Carolina, (1993) 63-76.
  * [7] J.N. Mordeson, D.S. Malik, N. Kuroki, Fuzzy Semigroups, Springer, 2003
  * [8] J.N. Mordeson, K.R. Bhutani, A. Rosenfeld, Fuzzy Group Theory, Springer, 2005
  * [9] E. Pasku, On a connection between fuzzy subgroups and F-inverse covers of inverse monoids, Novi Sad J. Math. First Online…
  * [10] A. Rosenfeld, Fuzzy groups, J. Math. Anal. Appl. 35 (1971), 512-517
  * [11] Saito, T. On semigroups which are semilattices of left simple semigroups, Math. Japon. 18 (1973), 95-97.
  * [12] O. Steinfeld, Quasi Ideals in Rings and Semigroups, Akademiai Kiado, Budapest, 1978
  * [13] L.A. Zadeh, Fuzzy sets, Inform. and Comput. 8 (1965), 338-353