# TASTy: A Transformer based Approach to Space and Time complexity

Kaushik Moudgalya
University of Montreal
Montreal, Quebec, Canada
&Ankit Ramakrishnan
Northeastern University
Boston, Massachusetts, USA
&Vamsikrishna Chemudupati
University of Montreal
Montreal, Quebec, Canada
&Xing Han Lu
McGill University
Montreal, Quebec, Canada

###### Abstract

Code based Language Models (LMs) have shown very promising results in the
field of software engineering with applications such as code refinement, code
completion and generation. However, the task of time and space complexity
classification from code has not been extensively explored due to a lack of
datasets, with prior endeavors being limited to Java. In this project, we aim
to address these gaps by creating a labelled dataset of code snippets spanning
multiple languages (Python and C++ datasets currently, with C, C#, and
JavaScript datasets being released shortly). We find that existing time
complexity calculation libraries and tools only apply to a limited number of
use-cases. The lack of a well-defined rule based system motivates the
application of several recently proposed code-based LMs. We demonstrate the
effectiveness of dead code elimination and increasing the maximum sequence
length of LMs. In addition to time complexity, we propose to use LMs to find
space complexities from code, and to the best of our knowledge, this is the
first attempt to do so. Furthermore, we introduce a novel code comprehension
task, called cross-language transfer, where we fine-tune the LM on one
language and run inference on another. Finally, we visualize the activation of
the attention fed classification head of our LMs using Non-negative Matrix
Factorization (NMF) to interpret our results.

##  1 Introduction

Language Models such as BERT, GPT-3, and T5 (Devlin et al., 2018; Brown et
al., 2020; Raffel et al., 2020) have propagated the idea of pre-training and
finetuning due to their success on a variety of downstream tasks. This has led
to a plethora of pre-trained models for programming languages (PL). These are
used on code related downstream tasks such as code search (Neelakantan et al.,
2022), code translation (Wang et al., 2021), code summarization (Parvez et
al., 2021) etc. We propose to work on one such downstream task: predicting
time and space complexities based on code.

Empirical methods of predicting time complexity involve running the same piece
of code over differently sized inputs and measuring the time taken for
execution, which enables us to approximate a function. Our attempt at
classification will help reduce the time and effort required in this process.
Additionally, we hope our attempt serves as a stepping stone for future
efforts that will remedy this issue once and for all. Finally, we wish to put
code-based LM’s code comprehension to the test by testing its cross-language
transfer capabilities, where we train our model to predict time complexities
on one language and evaluate on another. For even an average human programmer,
finding the time complexity for an arbitrary piece of code can be a cumbersome
task. Our long-term goals are two-fold:  1. Utilization of LM based complexity
predictors on competitive coding platforms, reducing the number of code runs
over differently sized inputs.  2. Integration of methods like ours with AI
programming assistants, which will make it easier for programmers to optimize
their code and ease the code review process.

Previous datasets with code and its time complexities, such as CoRCoD (Sikka
et al., 2020) and CodeComplex (Jeon et al., 2022) focus solely on Java. In
this paper, we introduce a C++ and Python dataset of code with both their
corresponding time and space complexities. This is the first dataset of its
kind for these languages with time complexities and as far as we know, the
first dataset ever to contain space complexities. A sample input and output of
our model are shown in Figure 1.111We plan to release similar datasets for C,
C# and JavaScript shortly.

Figure 1: Sample input program for time and space complexity calculation. The
expected time and space complexity model outputs would be Quadratic and
Constant respectively.

Most prior attempts to find time complexities are based on traditional machine
learning based methods such as Random Forests, Support Vector Machines (Sikka
et al., 2020) and Light Gradient Boosting Machines (CODAIT, 2021) bolstered by
manually constructed features. We believe learned attention weights might fare
better since the LMs can benefit from being exposed different code based
contexts which is infeasible with constructed features. Hence we evaluate
several code-based LMs on our dataset as well as the CodeComplex dataset.

The sole other attempt using LMs for time complexity prediction- Jeon et al.
(2022) uses techniques such as hierarchical attention and dead code
elimination. Often, the length of the code exceeds the maximum sequence length
of a transformer, which means that it cannot attend to all the tokens in the
code. Dead code elimination attempts to solve this problem by removing unused
methods and variables, which reduces the length of the code enabling
transformers to attend to more tokens. While verifying the efficacy of such
elimination, we wish to determine whether increasing sequence lengths (Beltagy
et al., 2020) increases the accuracy of our models.

If LMs can truly understand code at a conceptual level, models pre-trained on
multiple languages should be able to predict time complexity when we fine-tune
them on say, our Python based dataset and evaluate them on our C++ based
dataset. We believe this is reasonable since a competent human programmer who
has experience in multiple programming languages, would be able to calculate
time complexities for programs in all those languages.

Finally, we use Non-negative Matrix Factorization (NMF) to decompose the
activations of the Feed Forward Neural Network (FFNN) to extract interpretable
components as described in Alammar (2021). NMF affords researchers to probe
parts-to-whole relationships as described in Lee & Seung (1999). We use this
quality of NMF to qualitatively analyse the trained models.

We also present a survey of existing tools that predict time and space
complexity and detail our findings in Appendix A.1. Unfortunately, none of the
tools we found provide a comprehensive solution to the problem of identifying
algorithm complexities.

##  2 Related Work

CoRCoD: Sikka et al. (2020) created a dataset of 933 Java codes and their
complexities. We extend their work by making a dataset of C++ and Python
programs. Like our dataset, their code also seems to stem from GeeksforGeeks
based on the comments in the code. They classify programs into 5 classes:
$O(1)$, $O(n)$, $O(\log n)$, $O(n\log n)$, $O(n^{2})$. Their methods include
engineered features such as number of loops, number of if statements, maximum
depth of nested loops etc. extracted from the Abstract Syntax Tree.
Additionally, they also use graph2vec which uses a skipgram (Mikolov et al.,
2013) model to compute graph embeddings corresponding to code embeddings,
which are then classified using traditional ML methods such as Random Forests,
Support Vector Machines etc.

CODAIT (2021): Uses IBM’s CodeNet Dataset to predict time complexities. They
derive the labels by defining programs as sub-polynomial, polynomial or above-
polynomial (dataset is not publicly available). Like CorCoD, they engineer
features such as number of loops, breaks, if statements along with graph based
representations derived from an Abstract Syntax Tree. Their best performing
approach uses a 15 layer residual network which works on manually constructed
features concatenated with graph representations.

CodeComplex: (Jeon et al., 2022) construct a human annotated Java dataset
(CodeComplex) of 3803 Java codes and their time complexities (our dataset is
comprised of C++ and Python). We also note that this dataset has some overlap
with CoRCoD. Their approach combines dead-code elimination, multi-level pre-
training objectives such as loop depth prediction, number of parameters
prediction along with hierarchical attention which generates method level and
class level embeddings which are combined to create a final embedding for
prediction.

##  3 Our Dataset

We call our dataset the GeeksforGeeks (GFG) 222https://www.geeksforgeeks.org/
dataset, named after the site where the code was scraped. Our C++ and Python
dataset contain 1410 and 1373 codes and their corresponding time and space
complexities respectively. Check Table 1 for dataset class distribution. We
remark that our dataset is imbalanced and the linear class alone constitutes
54.6% and 55.8% of our Python and C++ time complexity datasets, while
combining the linear and quadratic classes constitutes 82.3% of both datasets.
There is a tendency on coding interview preparation platforms such as GFG to
curate more solutions around these complexities in order to be more
instructive. We do not exhaustively scrape the GFG website, thus, we could
potentially fix the high class imbalance with selective scraping. Other
statistics about the dataset such as construction details, the space
complexity class breakdown and statistics about the code length and its
distribution are mentioned in the Appendix A.2 and Appendix A.3 respectively.

Time Complexity | CoRCoD (Java) | CodeComplex (Java) | GFG (C++) | GFG (Python)
---|---|---|---|---
$O(1)$ | 143 | 533 | 33 | 35
$O(n)$ | 385 | 472 | 787 | 750
$O(n^{2})$ | 200 | 553 | 374 | 381
$O(n^{3})$ | - | 579 | 35 | 36
$O(\ln n)$ | 55 | 576 | 26 | 25
$O(n\ln n)$ | 150 | 518 | 127 | 121
NP-hard | - | 572 | 28 | 25
Total | 933 | 3803 | 1410 | 1373
Table 1: Comparison of the per class occurrences of time complexities across
different datasets CodeComplex and CoRCoD numbers borrowed from respective
papers.

##  4 Experiments

We consider BERT, CodeBERT, GraphCodeBERT, CodeT5 (Devlin et al., 2018; Feng
et al., 2020; Guo et al., 2020; Wang et al., 2021) and Longformer (Beltagy et
al., 2020) as our candidate models. CodeBERT, GraphCodeBERT and CodeT5 have
been pre-trained on CodeSearchNet (Husain et al., 2019), a dataset comprising
of 6 languages: Python, Java, JavaScript, PHP, Ruby and Go. CodeT5 has
additionally been trained on C and C# which their work sources from BigQuery
333https://console.cloud.google.com/ marketplace/details/github/github-repos.
All the models are fine-tuned by adding a linear layer (a classification head)
at the end to obtain the desired output. In addition to fine-tuning these
models on our GFG Python and GFG C++ datasets, we also fine-tune these models
for time complexity classification on the CodeComplex dataset.

For fine-tuning, we utilize the Adam (Kingma & Ba, 2014) optimizer with an
effective batch-size of 32; a default batch-size of 8 and 4 steps of gradient
accumulation (Andersson et al., 2022). Across all runs, we fine-tune for 15
epochs using a constant 1e-5 learning rate. We also employed mixed-precision
training for all models (Micikevicius et al., 2017) and gradient checkpointing
(Chen et al., 2016) for all models except CodeBERT. We use the base version of
all the models. All of our results are averaged across 5 runs.

For the CodeComplex dataset, we use the training and testing splits provided
by Jeon et al. (2022) with dead code elimination. For our GFG dataset, we use
a 80-20 label stratified train-test split for both time and space.

We consider the BERT results to be our baseline, since it is trained only on
Natural Language while the other models mentioned are trained either on both
Natural and Programming Languages or only Programming Languages. While the
Longformer too has only been trained on Natural Language, it has an inherent
advantage over BERT since it can attend to longer sequence lengths.

##  5 Results

###  5.1 Time & Space complexity results with constant maximum sequence length

We fine-tune the models mentioned in Table 2 except the Longformer with a
constant maximum sequence length of 512 tokens. We expected CodeT5 to achieve
the best accuracy since it has a higher number of learnable parameters, but
GraphCodeBERT achieves the best accuracy across all 3 datasets, on both time
and space. While the disparity in accuracies between BERT and the programming
language based models is quite significant on the CodeComplex dataset, the
disparity on the GFG C++ and GFG Python datasets is not so drastic. In fact,
CodeT5 does even worse than BERT on the GFG Python dataset, on both time and
space. We also report the average per-class accuracies across 5 runs in
Appendix A.4.

Table 2: Time and Space Complexity prediction results. We average test accuracies across 5 runs of all LMs. For Longformers, we vary the max. sequence length.  Language (Dataset) | Model |  | Max. Seq.
---
Length
Parameters |  | Accuracy
---
Time (%)
| Accuracy
---
Space (%)
Java (CodeComplex) | BERT | 512 | 110M | 84.68 | -
Java (CodeComplex) | CodeBERT | 512 | 125M | 90.54 | -
Java (CodeComplex) | GraphCodeBERT | 512 | 125M | 92.08 | -
Java (CodeComplex) | CodeT5 | 512 | 220M | 88.59 | -
C++ (GFG) | BERT | 512 | 110M | 75.60 | 74.75
C++ (GFG) | CodeBERT | 512 | 125M | 74.46 | 75.88
C++ (GFG) | GraphCodeBERT | 512 | 125M | 78.29 | 79.71
C++ (GFG) | CodeT5 | 512 | 220M | 71.56 | 70.28
Python (GFG) | BERT | 512 | 110M | 75.92 | 72.58
Python (GFG) | CodeBERT | 512 | 125M | 74.10 | 73.23
Python (GFG) | GraphCodeBERT | 512 | 125M | 77.89 | 73.96
Python (GFG) | CodeT5 | 512 | 220M | 68.43 | 65.16
Java (CodeComplex) | Longformer | 256 | 41M | 80.33 | -
Java (CodeComplex) | Longformer | 512 | 41M | 85.62 | -
Java (CodeComplex) | Longformer | 1024 | 41M | 85.75 | -
Java (CodeComplex) | Longformer | 2048 | 41M | 86.66 | -
C++ (GFG) | Longformer | 256 | 41M | 71.77 | -
C++ (GFG) | Longformer | 512 | 41M | 72.55 | -

###  5.2 Time complexity results with varying maximum sequence length

We fine-tune the Longformer model across a range of maximum sequence lengths
as shown in latter part of Table 2 and Figure 2. On both the GFG C++ and the
Java CodeComplex dataset, there is an increase in complexity prediction
accuracy with increasing sequence length.

Figure 2: Increasing accuracy with increasing maximum sequence length using
Longformers on the Java CodeComplex dataset.

While there is an observable increase in the accuracy with increasing sequence
length on the CodeComplex dataset, the extent of the improvement seems to
fizzle out. Similarly, on the GFG C++ dataset, the jump in accuracy while
going from 256 to 512 tokens is not comparable to the jump on the CodeComplex
dataset. However, note that Longformer is a Natural Language (NL) model, so
the fact that the accuracy does increase with increasing sequence length is
quite significant. In future work, we’d like to try exploring a PL based model
with larger sequence lengths.

###  5.3 Cross language transfer (CLT)

The results for CLT are given in Table 3. BERT has the best accuracies for
cross-language transfer on both the target languages, followed by
GraphCodeBERT on Python and Longformer (512) on C++.

Table 3: Cross-language transfer results: Inference of models trained on the CodeComplex (all sources are java) to target GFG Python (py) / C++ (cpp) datasets. No explicit fine-tuning was performed on the target language. Model | Parameters |  | Max.
---
Seq. Length
| Accuracy
---
py / cpp (%)
BERT | 110M | 512 |  29.13 / 23.54
CodeBERT | 125M | 512 | 19.37 / 16.80
GraphCodeBERT | 125M | 512 |  23.96 / 18.22
CodeT5 | 220M | 512 | 18.06 / 12.05
Longformer | 41M | 256 | 20.83 / 18.22
Longformer | 41M | 512 | 15.73 / 20.92
Longformer | 41M | 1024 | 13.83 / 13.19
Longformer | 41M | 2048 | 13.98 / 16.87

###  5.4 Dead code elimination

Introduced by Jeon et al. (2022), this technique removes variables, functions
etc. that are defined but not used, since scraped code need not be optimal
code. We observe a clear increase in the accuracy of LMs with dead code
elimination on the CodeComplex dataset Table 4, thus verifying the results
presented by Jeon et al. (2022). They report that CodeBERT model’s accuracy
jumps from 86.0% to 96.0% with pre-training, dead code elimination and
additional pre-training objectives. We ablated for the accuracy of dead code
elimination in our work.

Table 4: Ablating for the efficacy of Dead Code (DC) elimination on the CodeComplex dataset. Values without DC borrowed from Jeon et al. (2022). Values with DC are from Table 2. Model |  | Accuracy
---
w/o DC (%)
| Accuracy
---
w/DC (%)
CodeBERT | 86.0 | 90.54
GraphCodeBERT | 80.3 | 92.08
CodeT5 | 85.9 | 88.59

###  5.5 Qualitative analysis

We perform qualitative analyses based on the activations of two models,
CodeBERT and GraphCodeBERT. NMF is particularly suited to analysing text
qualitatively since it is able to provide us with interpretable components.
NMF has found success in medical research (Hamamoto et al., 2022) and
information retrieval González et al. (2010). In our case, we apply NMF to the
activations of the neurons across the FFNN layers. i.e. the classification
head on top of the LM.

The visualization in Figure 3 is an example of using this method (Alammar,
2021) on activations produced by CodeBERT after passing a ”hello world” java
program through it. It is clear by looking at the different components that
each component is activated by different items of syntax. For example,
component 1 in the figure is closely associated with the start line character
`<s>` and the character `</s>`. Component 7 is closely linked with access
specifiers in the code (`public class` and `public static`).

Identifying the number of components one should use for analysis depends on
the total length and complexity of the input. NMF solutions are non-unique and
we can get dissimilar results across different iterations. Depending on the
complexity of the input activations, we vary the number of components to
reveal fine-grained or global features of the input text. We compare models
across the three dimensions that follow:

Number of Components (Figure 3): Comparing the visualizations produced by a 3
component NMF and an 8 component NMF reveals that different components encode
for different kinds of syntax tokens. In the 3 component decomposition, we
observe three distinct sections that activate the neurons, the start and end
tokens; whitespace tokens such as newlines and tabs; and the main body of the
functions. With 8 components we observe an increase in the different semantic
units that different components react to. We now see the emergence of
components that react to access modifiers, identifier names, parenthesis and
individual functions.

(a) 3 components

(b) 8 components

Figure 3: Comparing visualizations with different number of components with
CodeBERT activations across all layers

Layers (Figure 4): Activations across the earlier layers result in components
with more variation and higher weights on average. Later layers are more
smooth and have lower weights. However, the semantic information conveyed by
the components appears to be identical.

(a) Layer 2 to 3 with 4 components

(b) Layer 9 to 10 with 4 components

Figure 4: Comparing visualizations of activations across different layers

Pre-Training Language (Figure 5) : We observe visualizations of layer
activations for GraphCodeBERT trained on Python. To generate these activations
we use a C++ sample and a Python sample. The components for both pairs of
languages appear to encode for similar things. For example, component 1
encodes the start and end tokens, components 5 in C++ and 2 in Python both
correspond to for-loop structures.

Figure 5: Comparing visualizations of activations where GraphCodeBERT was
trained on python. Here we test the model on C++ and Python code

##  6 Discussion

Comparison to traditional ML methods. In contrast to traditional ML methods
such as LGBM and Random Forests, we comprehensively explored LMs for our
complexity prediction task. We note that traditional ML approaches are not
easily parallelizable and cannot be trained on hundreds of thousands of data
points concurrently while such an impediment does not exist for LMs (Vaswani
et al., 2017). We also note that ML based approaches require extensive feature
engineering such as counting the number of ifs, loops, and breaks, finding
nested loop depths etc (Sikka et al., 2020). LMs have an inherent scalability
benefit along with the benefit of context without the need to create manual
features.

Natural Language vs. Programming Language models. While there is a trend of
increasing accuracy with increasing sequence length for Longformers on the
CodeComplex dataset (Table 2, Figure 2), we note that even Longformer (2048
sequence length) cannot surpass the accuracy of GraphCodeBERT (512 sequence
length). Observe that all the programming language (PL) based models
(CodeBERT, GraphCodeBERT and CodeT5) beat the Natural Language (NL) based
models (BERT and Longformer) on the CodeComplex dataset (Table 2). PL models
also beat NL models on the GFG C++ and Python dataset on both time and space
accuracies (Table 2) with CodeT5 being the sole exception. We also note the
efficacy of dead-code elimination which leads to at least a 2.69% increase in
accuracy across all LMs (Table 4).

CodeT5. Remark that CodeT5 is even outdone by BERT on both the GFG C++ and
Python datasets (Table 2). Furthermore, despite having a higher number of
parameters than all the other models used here, it does worse than even the
Longformer having 5x fewer parameters. On an unbalanced dataset, even majority
class predictors will achieve high accuracies, hence we will compare CodeT5 on
the balanced CodeComplex dataset. We would expect CodeT5 to surpass
GraphCodeBERT’s performance on CodeComplex since it has additional pre-
training objectives, a higher number of parameters and extra training data
(only model actually trained on C and C# which are similar to C++). Instead,
we believe that this provides further impetus to the arguments presented by
Wang et al. (2021), where they propose that the Bimodal Dual Generation pre-
training objective, while being great for PL-NL tasks such as code
summarization and code generation, might bias the model towards such tasks. At
its core, time and space complexity prediction are closer to a PL-PL task than
a PL-NL task. Hence, it might be interesting to see whether CodeT5 pre-trained
without the Bimodal Dual Generation objective continues to do worse than BERT
on our dataset.

Python vs. C++ Cross Language Transfer. We also note that Java to Python CLT
accuracies are better than Java to C++ CLT accuracies with two exceptions
Table 3, the Longformer (512) and Longformer (2048) results. This is explained
by the fact that the pre-training of all code based LMs used included Python
data but not C++ data (Code T5 uses C and C# data additionally). This explains
the outliers as well since it stems from a NL based LM (Longformer) rather
than a PL based LM, a pattern that is also supported by the BERT results in
Table 3, since BERT does better than CodeBERT, GraphCodeBERT and CodeT5. We
expected that Java to C++ CLT would be easier than Java to Python CLT since
syntactically Java as a language is closer to C++ than it is to Python.

NL vs. PL models on Cross Language Transfer. We conduct a completely novel
kind of code-understanding experiment, the CLT experiments (Table 3). We
expected our NL based models to give us almost random accuracies on this task,
which would amount to 14.28% (1 in 7); i.e. PL based LMs would do better than
NL based LMs. However, BERT was the best model on this task across both target
languages despite having not being pre-trained on programming languages.
Furthermore, the next best performer on Java to C++ CLT was the Longformer
(sequence length 512) model and we note that even the Longformer (sequence
length 256) model does better than most other PL based models. Interestingly,
on the Longformer models, it seems like there was a trend of decreasing CLT
performance with increasing sequence length until it bottomed out at the
random prediction level. We expected our PL based models to do way better than
they did since there are similarities across programming language structures
across languages such as classes, methods, loops, conditionals etc. Our
results lead us to think that existing models struggle to learn from the task
to generalize to another language. We believe that better predictions on this
task might tell us more about the representations learned by LMs.

##  7 Conclusion

In our work we address the lack of algorithmic complexity datasets by
publishing our GFG for C++ and Python. To the extent of our knowledge, this is
the first work to include space complexity data. We highlight the importance
of dead code elimination and increasing the sequence length to address the
issue of tokens that exceed maximum sequence length of LMs.

We also introduce a novel CLT task that can be used as an additional benchmark
for LM’s language comprehension capabilities. Finally, using NMF we
demonstrate that LMs can identify large several constructs in the code such as
for loop structures, access modifiers and individual functions.

While our indicate results that PL based models fare better on the complexity
prediction task, NL based models do better on CLT. However the difference in
the performance of NL and PL models is within 5-6% in both of these cases, so
there isn’t a clear winner. We’d like to try larger NL and PL models and also
larger PL models with a higher max sequence length.

Based on these results, code complexity prediction using a transformer based
approach seems promising. In future work, we plan to extend the GFG dataset by
adding more samples for each language and focusing on having a certain minimum
number of samples per class. This extension will enable us to perform the
fine-tuning and CLT experiments on a larger scale. We would also like to
extend the task to be solvable by generative models.

##  8 Ethical Considerations

All the code on GFG is a under a CCBY license which allows adaptation and
remixing as long as we attribute the original authors, while also allowing
commercial usage. The code in our dataset contains a comment line identifying
the original contributor wherever available.

## References

  * Agenis-Nevers et al. (2019) Marc Agenis-Nevers, Neeraj Dhanraj Bokde, Zaher Mundher Yaseen, and Mayur Shende.  Guesscompx: An empirical complexity estimation in r.  _arXiv_ , 2019.  URL https://github.com/agenis/GuessCompx.
  * Alammar (2021) J Alammar.  Ecco: An open source library for the explainability of transformer language models.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing: System Demonstrations_ , pp. 249–257, Online, August 2021. Association for Computational Linguistics.  doi: 10.18653/v1/2021.acl-demo.30.  URL https://aclanthology.org/2021.acl-demo.30.
  * Andersson et al. (2022) Axel Andersson, Nadezhda Koriakina, Nataša Sladoje, and Joakim Lindblad.  End-to-end multiple instance learning with gradient accumulation.  _arXiv preprint arXiv:2203.03981_ , 2022.  URL https://arxiv.org/pdf/2203.03981.pdf.
  * Beltagy et al. (2020) Iz Beltagy, Matthew E Peters, and Arman Cohan.  Longformer: The long-document transformer.  _arXiv preprint arXiv:2004.05150_ , 2020.  URL https://arxiv.org/pdf/2004.05150.pdf.
  * Berkes et al. (2011) Pietro Berkes, Finico, and Svisser etc.  big-O python module, 2011.  URL https://github.com/pberkes/big_O.
  * Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al.  Language models are few-shot learners.  _Advances in neural information processing systems_ , 33:1877–1901, 2020.  URL https://papers.nips.cc/paper/2020/hash/1457c0d6bfcb4967418bfb8ac142f64a-Abstract.html.
  * Chen et al. (2016) Tianqi Chen, Bing Xu, Chiyuan Zhang, and Carlos Guestrin.  Training deep nets with sublinear memory cost.  _arXiv preprint arXiv:1604.06174_ , 2016.  URL https://arxiv.org/abs/1604.06174.
  * CODAIT (2021) IBM CODAIT.  AI for code: Predict code complexity using IBM’s codenet dataset, 2021.  URL https://community.ibm.com/community/user/datascience/blogs/sepideh-seifzadeh1/2021/10/05/ai-for-code-predict-code-complexity-using-ibms-cod.
  * Devlin et al. (2018) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_ , 2018.
  * Feng et al. (2020) Zhangyin Feng, Daya Guo, Duyu Tang, Nan Duan, Xiaocheng Feng, Ming Gong, Linjun Shou, Bing Qin, Ting Liu, Daxin Jiang, and Ming Zhou.  CodeBERT: A pre-trained model for programming and natural languages.  In _Findings of the Association for Computational Linguistics: EMNLP 2020_ , pp. 1536–1547, Online, November 2020. Association for Computational Linguistics.  doi: 10.18653/v1/2020.findings-emnlp.139.  URL https://aclanthology.org/2020.findings-emnlp.139.
  * Frohn & Giesl (2017) Florian Frohn and Jürgen Giesl.  Complexity analysis for java with aprove.  In _International Conference on Integrated Formal Methods_ , pp. 85–101. Springer, 2017.  URL https://link.springer.com/chapter/10.1007/978-3-319-66845-1_6.
  * González et al. (2010) Fabio A. González, Juan C. Caicedo, Olfa Nasraoui, and Jaafar Ben-Abdallah.  Nmf-based multimodal image indexing for querying by visual example.  In _Proceedings of the ACM International Conference on Image and Video Retrieval_ , CIVR ’10, pp. 366–373, New York, NY, USA, 2010. Association for Computing Machinery.  ISBN 9781450301176.  doi: 10.1145/1816041.1816094.  URL https://doi.org/10.1145/1816041.1816094.
  * Guo et al. (2020) Daya Guo, Shuo Ren, Shuai Lu, Zhangyin Feng, Duyu Tang, Shujie Liu, Long Zhou, Nan Duan, Alexey Svyatkovskiy, Shengyu Fu, et al.  Graphcodebert: Pre-training code representations with data flow.  _arXiv preprint arXiv:2009.08366_ , 2020.  URL https://arxiv.org/pdf/2009.08366.pdf.
  * Hamamoto et al. (2022) Ryuji Hamamoto, Ken Takasawa, Hidenori Machino, Kazuma Kobayashi, Satoshi Takahashi, Amina Bolatkan, Norio Shinkai, Akira Sakai, Rina Aoyama, Masayoshi Yamada, Ken Asada, Masaaki Komatsu, Koji Okamoto, Hirokazu Kameoka, and Syuzo Kaneko.  Application of non-negative matrix factorization in oncology: one approach for establishing precision medicine.  _Briefings in Bioinformatics_ , 23(4), 07 2022.  ISSN 1477-4054.  doi: 10.1093/bib/bbac246.  URL https://doi.org/10.1093/bib/bbac246.  bbac246.
  * Husain et al. (2019) Hamel Husain, Ho-Hsiang Wu, Tiferet Gazit, Miltiadis Allamanis, and Marc Brockschmidt.  Codesearchnet challenge: Evaluating the state of semantic code search.  _arXiv preprint arXiv:1909.09436_ , 2019.  URL https://arxiv.org/pdf/1909.09436.pdf.
  * Jeon et al. (2022) Mingi Jeon, Seung-Yeop Baik, Joonghyuk Hahn, Yo-Sub Han, and Sang-Ki Ko.  Deep learning-based code complexity prediction.  2022\.
  * Kingma & Ba (2014) Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ , 2014.  URL https://arxiv.org/pdf/1412.6980.
  * Lacchia (2021) Michele Lacchia.  Radon, 2021.  URL https://pypi.org/project/radon/.
  * Lee & Seung (1999) Daniel D. Lee and H. Sebastian Seung.  Learning the parts of objects by non-negative matrix factorization.  _Nature_ , 401(6755):788–791, October 1999.  doi: 10.1038/44565.  URL https://doi.org/10.1038/44565.
  * Micikevicius et al. (2017) Paulius Micikevicius, Sharan Narang, Jonah Alben, Gregory Diamos, Erich Elsen, David Garcia, Boris Ginsburg, Michael Houston, Oleksii Kuchaiev, Ganesh Venkatesh, et al.  Mixed precision training.  _arXiv preprint arXiv:1710.03740_ , 2017.  URL https://arxiv.org/abs/1710.03740.
  * Mikolov et al. (2013) Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean.  Efficient estimation of word representations in vector space.  _arXiv preprint arXiv:1301.3781_ , 2013.  URL https://arxiv.org/pdf/1301.3781.pdf.
  * Neelakantan et al. (2022) Arvind Neelakantan, Tao Xu, Raul Puri, Alec Radford, Jesse Michael Han, Jerry Tworek, Qiming Yuan, Nikolas Tezak, Jong Wook Kim, Chris Hallacy, et al.  Text and code embeddings by contrastive pre-training.  _arXiv preprint arXiv:2201.10005_ , 2022.  URL https://arxiv.org/pdf/2201.10005.
  * Parvez et al. (2021) Md Rizwan Parvez, Wasi Uddin Ahmad, Saikat Chakraborty, Baishakhi Ray, and Kai-Wei Chang.  Retrieval augmented code generation and summarization.  _arXiv preprint arXiv:2108.11601_ , 2021.  URL https://arxiv.org/abs/2108.11601.
  * Raffel et al. (2020) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _The Journal of Machine Learning Research_ , 21(1):5485–5551, 2020.
  * Shunnarah (2020) Alec Shunnarah.  Big o notation calculator, 2020.  URL https://shunnarski.github.io/BigO.html.
  * Sikka et al. (2020) Jagriti Sikka, Kushal Satya, Yaman Kumar, Shagun Uppal, Rajiv Ratn Shah, and Roger Zimmermann.  Learning based methods for code runtime complexity prediction.  In _Advances in Information Retrieval: 42nd European Conference on IR Research, ECIR 2020, Lisbon, Portugal, April 14–17, 2020, Proceedings, Part I 42_ , pp. 313–325. Springer, 2020.  URL https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7148227/.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  _Advances in neural information processing systems_ , 30, 2017.
  * Wang et al. (2021) Yue Wang, Weishi Wang, Shafiq Joty, and Steven C.H. Hoi.  Codet5: Identifier-aware unified pre-trained encoder-decoder models for code understanding and generation.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pp. 8696–8708, Online and Punta Cana, Dominican Republic, November 2021. Association for Computational Linguistics.  doi: 10.18653/v1/2021.emnlp-main.685.  URL https://aclanthology.org/2021.emnlp-main.685.
  * Won (2020) Seok Won.  Big-O-Calculator, 2020.  URL https://pypi.org/project/big-O-calculator/.
  * Yin (2022) Terry Yin.  Lizard, 2022.  URL https://pypi.org/project/lizard/.

##  Appendix A Appendix

###  A.1 Extant tools to calculate Time and Space Complexities

There are several tools and calculators online that estimate algorithmic time
complexity but all of them have been designed with a very specific use-case in
mind. Our scraped code typically contains a complete code block with the
following components:  1. A function or class that has the solution to a
specific problem, say a function to rotate an array called ”Rotate”.  2.
Driver code that calls the above class or function and runs the code on all
the inputs to be tested.  None of the tools mentioned below accept the
complete code block described above. We do not wish to needlessly aid LMs in
any way in their pursuit to understand code, therefore, we expect that our LMs
will correctly perform complexity analysis despite these hurdles.

Python libraries such as Radon (Lacchia, 2021) and Lizard (Yin, 2022) compute
cyclomatic complexity, a quantitative measure of the number of linearly
independent paths in a program’s source code, computed using the control-flow
graph of a program. However, the number of linearly independent paths does not
represent how many times these paths were executed.

Big O Notation Calculator (Shunnarah, 2020) (Java, Javascript, C, C++, C#)
impressively calculates nested for loop complexities up to a depth of 4 (not
tested beyond this depth in this work) but is not designed to be used on on
classes or on complete code blocks .

The python library ”big-O-calculator” (Won, 2020) solely compares time
complexities of sorting algorithms.

A useful python module called big_O (Berkes et al., 2011) empirically computes
the time complexity by running a given function over differently sized inputs.
We plan to use this module in the future to increase the size of our dataset
as it will help us label scraped code which has no associated time complexity.
However, this will need additional processing, since it only accepts a Python
function as input which necessitates the removal of the driver code from the
program.

Aprove (Frohn & Giesl, 2017) was originally designed for termination analysis
of languages like Java, C, Haskell, Prolog. After some re-purposing, it was
adapted to also predict time complexities for Java programs. It works best on
numeric and heap manipulating programs, successfully classifying time
complexity in 73% of cases (212 total). It is not meant for programs which
contain floating point numbers or recursion.

The tools to compute or guess the space complexity of a program are far fewer,
the only one we could find was GuessCompx(Agenis-Nevers et al., 2019), an R
package which performs both time and space analysis empirically. This uses a
Generalized Linear Model (GLM) to fit a curve on empirically computed
complexity values based on LOO-MSE (leave one out-mean squared error).
Furthermore, this approach does not rely on the underlying code at all and
uses standard R functions: system.time and memory.size to perform its
analysis. Understandably, they do not include NP hard problems in their
empirical analysis. We are restricted to analyzing only R functions with this
package. We wish to do away with the empirical analysis of time and space
altogether, unless it is required to label some missing data as in the case
with the big_O python module.

The lack of a general tool to solve this problem is not surprising, since we
run into Turing’s Halting problem. This problem states that given an arbitrary
computer program and its input, it is not possible to determine whether the
program will finish execution or continue running forever. While deciding
whether a simple program will finish execution is straightforward, more
complex problems pose a problem. While we can check whether a program halts
execution after a few steps, if it does not, it is unknown whether the program
will finish execution or continue forever.

Based on the analysis above, we see that none of the tools are directly
applicable to the problem that we aim to solve except the big_O python module
which could help us label our missing data provided we only have the functions
to solve the problem and exclude the driver code.

###  A.2 Dataset construction details

We scrape all our data from geeksforgeeks (GFG). Under the GFG data structures
section, we obtain the links to data structure specific problems for arrays,
strings, stacks etc. The pages for each of these links contain a list of
problems for that specific data structure. We store these these problem links
in a dictionary like below:

⬇

dict_problem_urls = {

”arrays” : [url_problem_a, url_problem_b, …]

”trees” : [url_problem_c, url_problem_d, …]

}

We use a combination of beautifulsoup and regular expressions to scrape the
code and the associated time & space complexities from the page. If a page has
multiple codes and complexities, we obtain all of them. We ensure that the
right code is associated with the right complexities since there could be
multiple complexities for a given problem below the code block. To filter code
specific to each language, we look for telltale signs associated with a
language, such as comments and other HTML based identifiers on the source of a
web page, erring on the side of caution. Our scraper give us a pandas
dataframe, that contains the URL, code encoded in unicode (to preserve
formatting), time and space complexity (as html), the problem type (array /
stack / queue) and the comments (success / failure). In this manner we obtain
dataframes for C#, C++, Java, JavaScript and Python.

To obtain usable code from this dataframe, we decode the unicode data and then
perform unicode normalization using the unicodedata library which converts the
code along with the requisite formatting into usable text. To obtain the time
and space complexities from html, we use regular expressions along with
spreadsheet editors, since we needed to look at all our 1410 C++ samples and
1373 Python samples together to check whether a particular regular expression
logic worked. There were several cases which could not be tackled even using
regular expressions, so we had to manually visit the page and obtain those
complexities (approximately 500 samples in each programming language). We were
only able to perform this manual step for Python and C++, which is why we only
present statistics exclusively for these languages despite also having scraped
data in C#, Java and JavaScript. We also took this opportunity to manually
verify the veracity of around 700 samples for Python and C++.

###  A.3 Additional statistics about the dataset

Our space complexity dataset presented in Table 5 only has 6 classes compared
to the 7 classes for time complexity (cubic space complexity was not present
in the scraped data). Code length statistics based on length where length is
the string length of the code and where length is the number of lines of code
are given in Table 6 and Table 7 respectively. A visualization of the
distribution of code lengths (string length) is given in Figure 6 and Figure
7.

Table 5: Space Complexity class statistics Space Complexity | GFG (C++) | GFG (Python)
---|---|---
$O(1)$ | 602 | 603
$O(n)$ | 629 | 608
$O(n^{2})$ | 107 | 96
$O(\ln n)$ | 55 | 51
$O(n\ln n)$ | 3 | 3
NP-hard | 14 | 12
Total | 1390 | 1373
Table 6: Code length statistics for the GFG dataset. Here, length is measured akin to string length, as a count of the number of characters in code, not as the number of lines of code. Code length statistic | GFG (C++) | GFG (Python)
---|---|---
Mean | 1580.72 | 1323.84
Median | 1365.0 | 1122.0
Minimum | 242 | 195
Maximum | 6203 | 7900
Figure 6: Distribution of C++ code lengths, where length is the string based length of code Figure 7: Distribution of Python code lengths, where length is the string based length of code Table 7: Code length statistics based on the number of lines of code for the GFG dataset. Code length statistic | GFG (C++) | GFG (Python)
---|---|---
Mean | 66.84 | 55.05
Median | 58.0 | 48.0
Minimum | 12 | 11
Maximum | 223 | 216

###  A.4 Per class accuracies for time and space complexity prediction

In Table 8 , we report the per class test accuracies for our baseline model
BERT and our best model GraphCodeBERT on the GFG Python and GFG C++ Datasets,
averaged over 5 runs. We observe that our per class accuracies start high and
decrease in frequency order for the following classes: linear, quadratic,
$n\log n$, $\log n$. Despite there being a similar number of examples
(cpp/python) in the $\log n$ (26/25) and constant (33/25), cubic (35/36) and
NP-hard classes (28/25), we do not observe a similar level of accuracy across
these classes. While it is not surprising that our models have a hard time
understanding NP-hard problems, it is surprising that we observe low
accuracies on the constant class as well. We hope to remedy this issue in our
future work.

Table 8: Per class accuracies on the GFG C++ and Python datasets. All figures are test accuracy percentages for a particular class, averaged over 5 runs. Model | Dataset | $O(1)$ | $O(n)$ | $O(logn)$ | $O(n^{2})$ | $O(n^{3})$ |  $O(nlogn$) | NP
---|---|---|---|---|---|---|---|---
BERT | GFG - C++ | 5.7 | 86.8 | 40.0 | 76.5 | 14.2 | 64.0 | 0
GraphCodeBERT | GFG - C++ | 0 | 89.5 | 36.0 | 80.0 | 20.0 | 68.0 | 0
BERT | GFG - Python | 8.5 | 87.7 | 28.0 | 75.8 | 5.71 | 68.3 | 0
GraphCodeBERT | GFG - Python | 8.5 | 91.0 | 28.0 | 75.8 | 17.1 | 66.6 | 0


# Comparison of multi-mode Hong-Ou-Mandel interference and multi-slit
interference

Yan Guo  1,3 Zi-Xiang Yang  1,3 Zi-Qi Zeng  1 Chunling Ding  1 Ryosuke Shimizu
2and Rui-Bo Jin1  1Hubei Key Laboratory of Optical Information and Pattern
Recognition, Wuhan Institute of Technology, Wuhan 430205, China
2The University of Electro-Communications, 1-5-1 Chofugaoka, Chofu, Tokyo,
Japan
3These authors contributed equally to this work  *Corresponding author:
<EMAIL_ADDRESS>
###### Abstract

Hong-Ou-Mandel (HOM) interference of multi-mode frequency entangled states
plays a crucial role in quantum metrology. However, as the number of modes
increases, the HOM interference pattern becomes increasingly complex, making
it challenging to comprehend intuitively. To overcome this problem, we present
the theory and simulation of multi-mode-HOM interference (MM-HOMI) and compare
it to multi-slit interference (MSI). We find that these two interferences have
a strong mapping relationship and are determined by two factors: the envelope
factor and the details factor. The envelope factor is contributed by the
single-mode HOM interference (single-slit diffraction) for MM-HOMI (MSI). The
details factor is given by $\sin(Nx)/\sin(x)$ ($[\sin(Nv)/\sin(v)]^{2}$) for
MM-HOMI (MSI), where $N$ is the mode (slit) number and $x(v)$ is the phase
spacing of two adjacent spectral modes (slits). As a potential application, we
demonstrate that the square root of the maximal Fisher information in MM-HOMI
increases linearly with the number of modes, indicating that MM-HOMI is a
powerful tool for enhancing precision in time estimation. We also discuss
multi-mode Mach–Zehnder interference, multi-mode NOON-state interference, and
the extended Wiener-Khinchin theorem. This work may provide an intuitive
understanding of MM-HOMI patterns and promote the application of MM-HOMI in
quantum metrology.

††journal: oe††articletype: Research Article

http://www.qubob.com http://rs.pc.uec.ac.jp

##  1 Introduction

Since its discovery in 1987, the Hong-Ou-Mandel (HOM) interference using
downconverted biphotons has shown a wide variety of applications in quantum
optics [1, 2, 3, 4, 5]. In traditional HOM interference, the biphotons are
usually correlated in one discrete spectral mode. However, the biphotons
involved can be correlated in multiple discrete spectral modes, and this two-
body high-dimensional entangled state can be called entangled qudits [6, 7, 8,
9]. Here, we define the HOM interference using frequency entangled qudits as
the multi-mode HOM interference (MM-HOMI). One important characteristic of MM-
HOMI is that its interference patterns are significantly narrower than those
in single-mode HOM interference. Such narrow interference fringes provide more
Fisher information in phase estimation [10, 11, 12, 13, 14, 15]. As a result,
MM-HOMI is very promising in quantum metrology.

Recently, many works have been devoted to the study of HOM interference using
biphotons in multi-frequency modes. Lingaraju et al. investigated the effect
of spectral phase coherence of multi-frequency modes in HOM interference [13].
Chen et al. utilized HOM interference as a tool to characterize up to six-mode
frequency entangled qudits [14, 15]. Morrison et al. prepared an eight-mode
frequency entangled state in a customized poling crystal and tested its HOM
interference patterns [16]. In addition, HOM interference using biphoton
frequency combs, which have a large number of discrete frequency modes, has
also been widely investigated [17, 18, 19, 20].

However, as the mode number increases, the MM-HOMI pattern becomes more and
more complicated, which makes it challenging to understand intuitively. To
address this issue, we first present the theory and simulation of MM-HOMI and
then compare it with a well-known classical interference, the multi-slit
interference (MSI)[21, 22, 23, 24, 25]. We demonstrate that the MM-HOMI and
the MSI exhibit a strong mapping relationship.

Figure 1:  (a) The typical setup of multi-mode Hong-Ou-Mandel interference
(MM-HOMI). The signal (s) and idler (i) photons from an SPDC source impinge on
a beam splitter (BS) before the signal is delayed by a time $\tau$. The output
photons from the BS are detected by two single-photon detectors (D1 and D2),
which are connected to a coincidence counter ($\&$). For an MM-HOMI, the
biphotons have a multi-mode spectral distribution, as shown in the inset in
the bottom left corner. (b) The typical setup for a multi-slit interference.
The width of a single slit is $a$, and the width of a block is $b$; $a+b=d$.
For point $p$, the tilt angle of the incident light is $\theta$. The
interference pattern is observed on the screen.

##  2 The theory and simulation of MM-HOMI

The typical setup for HOM interference is shown in Fig. 1 (a). The signal and
idler photons generated from a spontaneous parametric downconversion (SPDC)
process can be expressed as [26, 27, 28]

$|\psi\rangle=\iint\nolimits_{-\infty}^{+\infty}d{\omega_{s}}d{\omega_{i}}f\left(\omega_{s},\omega_{i}\right)\hat{a}_{s}^{\dagger}\left(\omega_{s}\right)\hat{a}_{i}^{\dagger}\left(\omega_{i}\right)|0\rangle|0\rangle,$
(1)

where $f\left(\omega_{s},\omega_{i}\right)$ is the biphoton’s joint spectral
amplitude (JSA), $\omega$ is the angular frequency, and ${\hat{a}^{\dagger}}$
is the creation operator. The subscripts $s$ and $i$ represent the signal and
idler photons, respectively. In a HOM interference, the two-photon coincidence
probability $P\left(\tau\right)$ can be written as [29, 30]

$\begin{array}[]{lll}P\left(\tau\right)=\frac{1}{2}-\frac{1}{2}\iint\nolimits_{-\infty}^{+\infty}d{\omega_{1}}d{\omega_{2}}{\left|f\left({{\omega_{1}},{\omega_{2}}}\right)\right|^{2}}{\cos\left(\left({{\omega_{1}}-{\omega_{2}}}\right)\tau\right)},\end{array}$
(2)

where $\omega_{1}$ and $\omega_{2}$ are the frequencies detected by detectors
D1 and D2 in Fig. 1 (a). For simplicity, in the above equation, we have
assumed that $f\left(\omega_{1},\omega_{2}\right)$ is normalized and satisfies
the exchanging symmetry of
$f\left(\omega_{1},\omega_{2}\right)=f\left(\omega_{2},\omega_{1}\right)$. See
the Appendix for more details.

In the MM-HOMI, the JSA can be written as:

$\begin{array}[]{l}f\left({{\omega_{1}},{\omega_{2}}}\right)=\sum\limits_{k=1}^{N}{{f_{0}}\left({{\omega_{1}}-{\omega_{0}}-\left({2k-N-1}\right)\alpha,{\omega_{2}}-{\omega_{0}}+\left({2k-N-1}\right)\alpha}\right)},\\\
\end{array}$ (3)

where $f_{0}\left({\omega_{1}},{\omega_{2}}\right)$ is an arbitrary
distribution function of the single spectral mode, $N$ is the mode number,
$\alpha$ represents the mode spacing, and $\omega_{0}$ is the mode’s central
frequency. As calculated in the Appendix, $P\left(\tau\right)$ can be
simplified as

$\begin{array}[]{lll}P\left(\tau\right)&=\frac{1}{2}\left[1-\frac{1}{{N}}\frac{{\sin(2N\alpha\tau)}}{{\sin(2\alpha\tau)}}\iint\nolimits_{-\infty}^{\infty}{d{\omega_{1}}}d{\omega_{2}}{f_{0}}^{2}\left({{\omega_{1}},{\omega_{2}}}\right)\cos\left({\left({{\omega_{1}}-{\omega_{2}}}\right)\tau}\right)\right]\\\
&=\frac{1}{2}\left[1-P_{0}\frac{{{\rm{\sin}}\left({Nx}\right)}}{{{\rm{\sin}}\left({x}\right)}}\right],\\\
\end{array}$ (4)

where $x=2\alpha\tau$, which corresponds to the phase spacing caused by two
adjacent spectral modes.
$P_{0}=\frac{1}{{N}}\iint\nolimits_{-\infty}^{\infty}{d{\omega_{1}}}d{\omega_{2}}{f_{0}}^{2}\left({{\omega_{1}},{\omega_{2}}}\right)\cos\left({\left({{\omega_{1}}-{\omega_{2}}}\right)\tau}\right)$
corresponds to the envelope of the interference patterns.

We can observe in Eq. (4) that the MM-HOMI is determined by two factors: the
envelope factor $P_{0}$ and the details factor
$\frac{{{\rm{\sin}}\left({Nx}\right)}}{{{\rm{\sin}}\left({x}\right)}}$.
$P_{0}$ is contributed by the single-mode HOM interference (for N=1). $P_{0}$
can also be expressed in the form of a Fourier transformation by projecting
${f_{0}}^{2}\left({{\omega_{1}},{\omega_{2}}}\right)$ on the axis of
$\omega_{1}-\omega_{2}$, as shown in Eq. (23) in the Appendix.

For simplicity, we can set $\;f\left({{\omega_{1}},{\omega_{2}}}\right)$ to a
multi-mode Gaussian distribution[16, 31]:

$\begin{array}[]{l}f\left({{\omega_{1}},{\omega_{2}}}\right)=\mathop{\sum}\limits_{k=1}^{N}\exp\left[-\frac{{{{({\omega_{1}}-{\omega_{0}}-\left({2k-N-1}\right)\alpha)}^{2}}}}{{{\gamma^{2}}}}-\frac{{{{({\omega_{2}}-{\omega_{0}}+\left({2k-N-1}\right)\alpha)}^{2}}}}{{{\gamma^{2}}}}\right],\\\
\end{array}$ (5)

where $N$ is the mode number, $\gamma$ represents the mode width. In a real
experiment, $\gamma$ and $\alpha$ are determined by the width of the pump and
the phase-matching function of the crystal [16]. As calculated in the
Appendix, $P_{0}\left(\tau\right)$ can be simplified as

$\begin{array}[]{lll}P_{0}=\frac{1}{{N}}\exp\left(-\frac{{{\gamma^{2}}{\tau^{2}}}}{4}\right).\end{array}$
(6)

Figure 2: Theoretical simulations of MM-HOMI and MSI. (a1-a8): The JSA of the
biphotons with mode numbers ranging from 1 to 8, with$\;\alpha$=5
rad$\cdot$THz and $\gamma=2$ rad$\cdot$THz. (b1-b8) : The MM-HOMI patterns
based on the JSA shown in (a1-a8). (c1-c8): The slit distribution for $N=1-8$,
with $a=1\times 10^{-5}$m and $d=5\times 10^{-4}$m. (d1-d8): The MSI patterns
based on the slit distribution in (c1-c8).

According to Eq. (4), Eq. (5) and Eq. (6), we can plot the interference
patterns of MM-HOMI. As shown in Fig. 2, the first column is the JSA of the
biphotons, and the mode number is 1, 3, 5, 7, 2, 4, 6, and 8. Here, we choose
the unit ellipticity for each mode, since this is the simplest case and has
been realized in experiment [16]. The second column is the corresponding MM-
HOMI pattern.

Firstly, we compare the envelopes of the interference patterns. The odd-number
MM-HOMI patterns have an asymmetric envelope, whereas the even-number MM-HOMI
patterns are symmetric to the line of $P\left(\tau\right)=0.5$. This is due to
the characteristics of the function
$\frac{\sin\left(Nx\right)}{\sin\left(x\right)}$, which is asymmetric
(symmetric) when N is an odd (even) number.

Secondly, we compare the primary and secondary valley (peak) numbers. For the
odd-number MM-HOMI patterns, there are (N-3)/2 secondary valleys (for N$>$3)
between two primary valleys, while for the even-number MM-HOMI patterns, there
are N-2 secondary valleys (for N$>$2) between two primary valleys.

##  3 Comparison of MM-HOMI and MSI

So far, we have analyzed the properties of the MM-HOMI. However, we can notice
that the interference patterns in Fig. 2 are very complicated. One might gain
some insight by comparing MM-HOMI with a classical well-known multi-slit
interference (MSI). It may be intuitive to understand that the multiple
spectra function in a manner similar to the multiple slits.

Next, we deduce the mathematical form of MSI and compare it with MM-HOMI.

The typical setup for MSI is shown in Fig. 1 (b). Here, the number of slits is
$N$, the slit width is $a$, the interval of the slits is $b$, and $a+b=d$. As
calculated in the Appendix, the amplitude of the diffraction pattern at point
$p$ is

$\begin{array}[]{lll}A_{p}={A_{0}}\frac{{\sin\left(u\right)}}{u}\frac{{\sin\left(Nv\right)}}{{\sin\left(v\right)}},\end{array}$
(7)

where $A_{0}$ is a constant determined by the power of the light source, the
distance between the slit and the screen, and the size of the slit [21].
$u=\frac{{\pi a\sin\theta}}{\lambda}$ represents the phase difference in one
slit. $v=\frac{{\pi d\sin\theta}}{\lambda}$ represents the phase difference
between two adjacent slits. $\lambda$ is the wavelength of the input light and
$\theta$ is the tilt angle of the light, as shown in Fig. 1 (b). For
simplicity, we can set $A_{0}=1$. The intensity of the diffraction pattern is:

$\begin{array}[]{lll}I={\mid
A_{p}\mid}^{2}=\left(\frac{\sin\left(u\right)}{u}\right)^{2}\left(\frac{\sin\left(Nv\right)}{\sin\left(v\right)}\right)^{2}=I_{0}\left(\frac{\sin\left(Nv\right)}{\sin\left(v\right)}\right)^{2},\\\
\end{array}$ (8)

where ${I_{0}}=\left(\frac{{\sin}{\left(u\right)}}{u}\right)^{2}$ is the
intensity due to one-slit diffraction, which is also the interference
pattern’s envelope.

According to Eq. (8), we can plot the interference patterns of MSI, as shown
in the third and fourth columns in Fig. 2. The parameters are listed in detail
in the caption of Fig. 2. There are N-2 secondary peaks (for N$>$2) between
two primary peaks in the fourth column of Fig. 2. This is comparable to the
even-number MM-HOMI patterns, which also have N-2 secondary valleys (for
N$>$2) between two primary valleys.

Figure 3: (a1-a3): The JSA of the biphotons with mode spacing of $\alpha$=5
rad$\cdot$THz and mode sizes of $\gamma$= 0.5 rad$\cdot$THz, 2.5
rad$\cdot$THz, and 4.5 rad$\cdot$THz, respectively. (b1-b3): The calculated
HOMI patterns using the JSA in (a1-a3). (c1-c3): The 4-slit distributions with
$d=5\times 10^{-4}$m and $a=1\times 10^{-4}$m, $1.5\times 10^{-4}$m, and
$2\times 10^{-4}$m, respectively. (d1-d3): The calculated MSI patterns using
the slits in (c1-c3).

Next, we investigate the influence of the mode size in MM-HOMI and MSI. Figure
3 (a1-a3, b1-b3) displays the JSA of the biphotons and the corresponding MM-
HOMI. Here, we set $\alpha$ to be fixed at 5 rad$\cdot$THz, and $\gamma$ to be
0.5 rad$\cdot$THz, 2.5 rad$\cdot$THz, and 4.5 rad$\cdot$THz, respectively. It
can be observed that with the increase of $\gamma$, the envelope becomes
narrower, but the spacing of adjacent peaks (valleys) does not change. This
phenomenon can be well explained by Eq. (4). Figure 3 (c1-c3, d1-d3) shows the
4-slit distributions and the corresponding MSI. It can be noticed that the
envelope also becomes narrower with the increase of $a$, which is similar to
the phenomenon of MM-HOMI.

Figure 4:  (a1-a3): The JSA of biphotons with mode size of $\gamma=2$
rad$\cdot$THz and mode spacing of $\alpha$=2.5 rad$\cdot$THz, 5 rad$\cdot$THz
and 7.5 rad$\cdot$THz, respectively. (b1-b3): The calculated MM-HOMI patterns
using the JSA in (a1-a3). (c1-c3): The 4-slit distributions with $a=1.5\times
10^{-4}$m, and $d=3\times 10^{-4}$m, $6\times 10^{-4}$m, $9\times 10^{-4}$m,
respectively. (d1-d3): The calculated MSI patterns using the slits in (c1-c3).

Then, let us examine the impact of mode spacing on MM-HOMI and MSI. Figure 4
(a1-a3, b1-b3) depicts the JSA and MM-HOMI of biphotons with $\gamma$ fixed at
2 rad$\cdot$THz and $\alpha$ increasing from 2.5 rad$\cdot$THz to 5
rad$\cdot$THz and 7.5 rad$\cdot$THz. Figure 4 (c1-c3, d1-d3) shows the slit
distributions and the corresponding MSI. By comparing (a1-b3) with (c1-d3), we
can observe that the envelope remains constant, while the number of peaks and
valleys increases as mode spacing increases. These phenomena can also be well
explained by Eq. (4) and Eq. (8).

After analyzing Figs. (4, 5, 6) and Eqs. (4, 8), we can confirm that the MM-
HOMI and MSI have a strong mapping relationship, as summarized in Tab. 1. The
phase variable $x$, which accumulates in the time domain, represents the phase
spacing between two spectra modes in the MM-HOMI; while the phase variable
$v$, which accumulates in the space domain, represents the phase spacing
between two slits in the MSI. Both MM-HOMI and MSI are determined by two
factors: the envelope factor and the details factor. The details factor
includes a common term of
$\frac{{{\rm{\sin}}\left({Nx}\right)}}{{{\rm{\sin}}\left({x}\right)}}$ with a
mode number of $N$. In MM-HOMI, the envelope factor $P_{0}$ corresponds to the
HOM interference of a single spectral mode, and $P_{0}$ is also related to the
Fourier transform of a single spectral mode, as shown in Eq. (23). Similarly,
the details factor $I_{0}$ corresponds to the single-slit diffraction, and it
is also contributed by the Fourier transform of a single slit, as explained in
Eq. (28) in the Appendix. Therefore, we can conclude that the multiple spectra
indeed function similarly to the multiple slits, as we expected at the
beginning of this section. Consequently, the mapping relationship really can
help on the intuitive understanding of the MM-HOMI.

Table 1: The mapping relationship between MM-HOMI and MSI. |  MM-HOMI $P=\frac{1}{2}\left[1-P_{0}\frac{{{\rm{\sin}}\left({Nx}\right)}}{{{\rm{\sin}}\left({x}\right)}}\right]$ |  MSI $I=I_{0}\left(\frac{{\sin}\left(Nv\right)}{{\sin}{\left(v\right)}}\right)^{2}$
---|---|---
variable | $x=2\alpha\tau$ | $v=\frac{{\pi d\sin\theta}}{\lambda}$
domain | frequency ($\alpha$) $\leftrightarrow$ time ($\tau$) | spatial frequency ($\frac{{\sin\theta}}{\lambda}$)$\leftrightarrow$space ($d$)
phase |  $x$: phase spacing of two spectra |  $v$: phase spacing of two slits
mode number | $N$ | $N$
details factor | $\frac{\sin\left(Nx\right)}{\sin\left(x\right)}$ | $\left(\frac{\sin\left(Nv\right)}{\sin\left(v\right)}\right)^{2}$
envelope factor |  $P_{0}$: single-mode HOMI |  $I_{0}$: single-slit diffraction
Fourier transform |  $P_{0}$: FT of single spectral mode |  $I_{0}$: FT of single slit

##  4 Application of MM-HOMI in quantum meteorology

MSI has numerous applications in optical measurement, with one typical example
being the diffraction-grating-based spectrometer. The resolving power of a
diffraction grating is proportional to the total number of slits (or grooves)
on the grating [21, 22, 23, 24, 25]. Inspired by this feature, here we
consider the resolving power of a MM-HOMI in quantum metrology by increasing
the total number of the spectral modes.

The ultimate limit on the precision of time estimation is the Cramér-Rao bound
[12, 32] , which states that the variance of any unbiased estimator is bounded
by

$Var(\tilde{t})\geq\frac{1}{{Num\times FI}},$ (9)

where $\tilde{t}$ is the estimator of time $t$, and $Num$ is the number of
measurement times and $FI$ is the Fisher information (FI). For a single
measurement, $Num$=1. So, the standard deviation (SD) is bound by

$SD(\tilde{t})\geq\frac{1}{{\sqrt{FI}}}.$ (10)

FI of a single interference fringe can be calculated as [10, 33]:

$FI\left(\tau\right)=P\left(\tau\right)\left({\frac{{\partial\left[\ln
P\left(\tau\right)\right]}}{{\partial\tau}}}\right)^{2}+\left[1-P\left(\tau\right)\right]\left({\frac{{\partial\left[\ln\left(1-P\left(\tau\right)\right)\right]}}{{\partial\tau}}}\right)^{2}=\frac{\left[{P^{\prime}\left(\tau\right)}\right]^{2}}{{P\left(\tau\right)\left[1-P\left(\tau\right)\right]}}.$
(11)

By using Eq.(4) and Eq.(11), we can obtain the Fisher information of MM-HOMI
as

$\begin{array}[]{lll}FI\left(\tau\right)=\frac{{{{\left({\frac{{{\gamma^{2}}\tau}}{2}\sin\left({2\alpha
N\tau}\right)-2\alpha N\cos\left({2\alpha
N\tau}\right)+2\alpha\sin\left({2\alpha
N\tau}\right)\cot\left({2\alpha\tau}\right)}\right)}^{2}}}}{{{N^{2}}\exp[\frac{{{\gamma^{2}}{\tau^{2}}}}{2}]{{\sin}^{2}}\left({2\alpha\tau}\right)-{{\sin}^{2}}\left({2\alpha
N\tau}\right)}}.\end{array}$ (12)

Figure 5(a1-a8) displays the simulated FI of the $P\left(\tau\right)$ in Fig.
2(b1-b8), with the mode number N increasing from 1 to 8. The single valley in
Fig. 2(b8) is transferred to a double peak in Fig. 5(a8). Figure 6 summarizes
the square root of maximal FI as a function of the mode number N ranging from
1 to 40. It is evident that the square root of maximal FI increases linearly
with the increase in mode number. This suggests that increasing the mode
number is a powerful method to improve precision in time or phase estimation.

Figure 5:  The Fisher information of MM-HOMI with a mode number ranging from 1
to 8 in (a1-a8), with$\;\alpha$=5 rad$\cdot$THz and $\gamma=2$ rad$\cdot$THz.
Figure 6:  The square root of maximal Fisher information with mode numbers
ranging from 1 to 40, with$\;\alpha$=5 rad$\cdot$THz and $\gamma=2$
rad$\cdot$THz. The blue line is a linear fit.

##  5 Discussion

From the viewpoint of the extended Wiener-Khinchin theorem (e-WKT) [30], the
Fourier transform of the HOM interference pattern is determined by the
difference–frequency distribution of the JSI, i.e., the projection of
$f\left({{\omega_{1}},{\omega_{2}}}\right)$ onto the $\omega_{1}-\omega_{2}$
axis. The e-WKT is not only applicable to the single-mode case but also
explains the multi-mode case in this study. Specifically, the interference
patterns of MM-HOMI are determined by the Fourier transform of the
difference–frequency distribution of the multi-mode JSI.

To gain a deeper understanding of the multi-mode effect, we also compared the
MM-HOMI and MSI with two other important interferences in quantum optics: the
multi-mode Mach–Zehnder interference (MM-MZI) and the multi-mode NOON state
interference (MM-NOONSI), using the setups shown in Fig. 7 (a, b). Here, the
NOON-state is a $(\left|{20}\right\rangle+\left|{02}\right\rangle)/\sqrt{2}$
state, which has a photon number of 2, but with a spectral-mode number of N,
as shown in Fig. 7(e1-e8). As calculated in the Appendix, the single count in
a MM-MZI can be expressed as

$\begin{array}[]{l}P_{MZI}\left(\tau\right)=\frac{1}{2}+\frac{1}{{2N}}\exp\left[{-\frac{{{\gamma^{2}}{\tau^{2}}}}{8}}\right]\frac{{\sin\left({N\alpha\tau}\right)}}{{\sin\left({\alpha\tau}\right)}}\cos\left({{\omega_{0}}\tau}\right),\\\
\end{array}$ (13)

and the coincidence counts in a MM-NOONSI can be expressed as

$\begin{array}[]{l}P_{NOON}\left(\tau\right)=\frac{1}{2}+\frac{1}{{2N}}\exp\left[-\frac{{{\gamma^{2}}{\tau^{2}}}}{4}\right]\frac{{\sin\left({2N\alpha\tau}\right)}}{{\sin\left({2\alpha\tau}\right)}}\cos\left({2{\omega_{0}}\tau}\right).\\\
\end{array}$ (14)

In the above two models, Gaussian envelopes were chosen for simplicity. Refer
to the Appendix for deductions using arbitrary envelopes. The parameters are
listed in detail in the caption of Fig. 7. By comparing the theoretical
simulations in Fig. 7 (d1-d8) and (f1-f8), we observe that there are N-2
secondary peaks (for N $>$ 3) between the two main peaks in N-mode
Mach–Zehnder interference and N-mode NOON-state interference.

By comparing Eq. (13), Eq. (14), Eq. (4), and Eq. (8), we observe that the MM-
MZI and MM-NOONSI are also contributed by the details factor of
$\sin\left(Nx\right)/\sin\left(x\right)$, but multiplied by a factor of
$\cos\left(\omega_{0}\tau\right)$ or $\cos\left(2\omega_{0}\tau\right)$. In
general, the connection between the MM-HOMI, the MSI, the MM-MZI, and the MM-
NOONSI is that all these interferences are contributed by N input modes in
physics and determined by the factor of
$\sin\left(Nx\right)/\sin\left(x\right)$ in mathematics.

Figure 7:  (a): The typical setup of Mach-Zehnder interference. (b): The
typical setup of NOON-state interference. (c1-c8): The spectral amplitude of
the light source for multi-mode Mach–Zehnder interference. (d1-d8): The multi-
mode Mach–Zehnder interference patterns for mode numbers $N=1\sim 8$
with$\;\alpha$=5 rad$\cdot$THz and $\gamma=2$ rad$\cdot$THz. (e1-e8): The
joint spectral amplitude of the biphotons for the multi-mode NOON state
interference. (f1-f8): The multi-mode NOON state interference patterns for
mode numbers $N=1-8$ with$\;\alpha$=5 rad$\cdot$THz and $\gamma=2$
rad$\cdot$THz.

##  6 Conclusion

In conclusion, we have presented the theory and simulation of MM-HOMI and
compared them with MSI. We confirm that both interferences are determined by
two factors: the envelope factor and the details factor. For MM-HOMI (MSI),
the envelope factor is determined by each mode (slit), while the details
factor is determined by the N modes (slits). The mapping relationship between
MM-HOMI and MSI may provide an intuitive explanation of MM-HOMI. As an example
of its application, we demonstrate that the square root of maximal Fisher
information in a MM-HOMI increases linearly with the increase of mode numbers,
indicating that increasing the mode number is a potent method for enhancing
precision in quantum metrology.

## Appendix

## A1:The calculation of multi-mode HOM interference

In this section, we deduce the equation of HOMI using a biphoton state with a
multi-mode distribution. The joint spectral amplitude (JSA) of the biphoton
state from an SPDC source can be expressed
as$f\left(\omega_{s},\omega_{i}\right)$, and the input two-photon state is

$\begin{array}[]{lll}\left|\psi\right\rangle=\iint_{-\infty}^{+\infty}{d\omega_{s}}d\omega_{i}f\left(\omega_{s},\omega_{i}\right){\hat{a}}_{s}^{\dagger}\left(\omega_{s}\right){\hat{a}}_{i}^{\dagger}\left(\omega_{i}\right)\left|00\right\rangle,\end{array}$
(15)

where the subscripts $s$ and $i$ denote the signal and idler photons,
respectively, and$\ {\hat{a}}^{\dagger}\left(\omega\right)$is the creation
operator of the signal and idler photons at angular frequency $\omega$. The
detection field operators of detector 1 (D1) and detector 2 (D2) are
${\hat{E}}_{1}^{\left(+\right)}\left(t_{1}\right)=\frac{1}{\sqrt{2\pi}}\int_{0}^{\infty}{d\omega_{1}{\hat{a}}_{1}\left(\omega_{1}\right)e^{-i{\omega_{1}}{}t_{1}}}$
and
$\hat{E}_{2}^{\left(+\right)}\left(t_{2}\right)=\frac{1}{\sqrt{2\pi}}\int_{0}^{\infty}{d\omega_{2}{\hat{a}}_{2}\left(\omega_{2}\right)e^{-i\omega_{2}t_{2}}}$,
where subscripts 1 and 2 denote the photons detected by $D1$ and $D2$,
respectively. The transformation rule of a 50/50 beam splitter (BS) after a
delay time $\tau$ is
${\hat{a}}_{1}\left(\omega_{1}\right)=\frac{1}{\sqrt{2}}\left[{\hat{a}}_{s}\left(\omega_{1}\right)+{\hat{a}}_{i}\left(\omega_{1}\right)e^{-i\omega_{1}\tau}\right]$
and
${\hat{a}}_{2}\left(\omega_{2}\right)=\frac{1}{\sqrt{2}}\left[{\hat{a}}_{s}\left(\omega_{2}\right)+{\hat{a}}_{i}\left(\omega_{2}\right)e^{-i\omega_{2}\tau}\right]$.
So, we can rewrite the field operators as

$\begin{array}[]{lll}{\hat{E}}_{1}^{\left(+\right)}\left(t_{1}\right)=\frac{1}{\sqrt{4\pi}}\int_{-\infty}^{+\infty}{d\omega_{1}}\left[{\hat{a}}_{s}\left(\omega_{1}\right)e^{-i\omega_{1}t_{1}}+{\hat{a}}_{i}\left(\omega_{1}\right)e^{-i\omega_{1}(t_{1}+\tau)}\right],\end{array}$
(16)
$\begin{array}[]{lll}{\hat{E}}_{2}^{\left(+\right)}\left(t_{2}\right)=\frac{1}{\sqrt{4\pi}}\int_{-\infty}^{+\infty}{d\omega_{2}}\left[{\hat{a}}_{s}\left(\omega_{2}\right)e^{-i\omega_{2}t_{2}}+{\hat{a}}_{i}\left(\omega_{2}\right)e^{-i\omega_{2}(t_{2}+\tau)}\right].\end{array}$
(17)

As calculated in the supplementary materials of Ref. [Optica 5, 93-98 (2018)],
the two-photon coincidence probability $P\left(\tau\right)$ is

$\begin{array}[]{lll}P\left(\tau\right)&=\iint\nolimits_{-\infty}^{+\infty}dt_{1}dt_{2}\langle\psi|{\hat{E}}_{1}^{(-)}{\hat{E}}_{2}^{(-)}{\hat{E}}_{2}^{(+)}{\hat{E}}_{1}^{\left(+\right)}|\psi\rangle\\\
&=\frac{1}{4}\iint\nolimits_{-\infty}^{+\infty}{d\omega_{1}d\omega_{2}\left|f\left(\omega_{1},\omega_{2}\right)-f\left(\omega_{2},\omega_{1}\right)e^{-i\left(\omega_{1}-\omega_{2}\right)\tau}\right|^{2}}.\end{array}$
(18)

For simplicity, we can consider $f\left(\omega_{1},\omega_{2}\right)$ to be
real and normalized, i.e.,
$f\left(\omega_{1},\omega_{2}\right)=f^{*}\left(\omega_{1},\omega_{2}\right)$
and
$\iint_{-\infty}^{\infty}{d\omega_{1}d\omega_{2}\left|f\left(\omega_{1},\omega_{2}\right)\right|^{2}}=1$,
then

$\begin{array}[]{lll}P\left(\tau\right)=\frac{1}{2}-\frac{1}{2}\iint\nolimits_{-\infty}^{+\infty}{d\omega_{1}d\omega_{2}}\left[f\left(\omega_{2},\omega_{1}\right)f\left(\omega_{1},\omega_{2}\right)\cos((\omega_{1}-\omega_{2})\tau)\right].\par\end{array}$
(19)

In the MM-HOMI, a multi-mode JSA can be written as:

$\begin{array}[]{l}f\left({{\omega_{1}},{\omega_{2}}}\right)=\sum\limits_{k=1}^{N}{{f_{0}}\left({{\omega_{1}}-{\omega_{0}}-\left({2k-N-1}\right)\alpha,{\omega_{2}}-{\omega_{0}}+\left({2k-N-1}\right)\alpha}\right)},\\\
\end{array}$ (20)

where $f_{0}\left({\omega_{1}},{\omega_{2}}\right)$ is an arbitrary
distribution function of the single mode, $N$ is the mode number, $\alpha$
represents the mode spacing, and $\omega_{0}$ is the mode’s central frequency.
Then

$\begin{array}[]{lll}P\left(\tau\right)&=\frac{1}{2}-\frac{1}{2}\int{\int_{0}^{\infty}{d{\omega_{1}}}}d{\omega_{2}}\\\
&\left[{({\sum\limits_{k=1}^{N}{{f_{0}}\left({{\omega_{1}}-{\omega_{0}}-\left({2k-N-1}\right)\alpha,{\omega_{2}}-{\omega_{0}}+\left({2k-N-1}\right)\alpha}\right)}})^{2}}\cos({\omega_{1}}-{\omega_{2}})\tau\right].\par\par\end{array}$
(21)

If the mode width is much smaller than the mode spacing, the cross terms can
be ignored, then

$\begin{array}[]{lll}&P\left(\tau\right)\\\
&=\frac{1}{2}-\frac{1}{{2N}}\sum\limits_{k=1}^{N}{\int{\int_{-\infty}^{\infty}{d{\omega_{1}}}}d{\omega_{2}}{f_{0}}^{2}\left({{\omega_{1}}-{\omega_{0}}-\left({2k-N-1}\right)\alpha,{\omega_{2}}-{\omega_{0}}+\left({2k-N-1}\right)\alpha}\right)}\\\
&\quad\times\cos\left({({\omega_{1}}-{\omega_{2}})\tau}\right)\\\
&=\frac{1}{2}-\frac{1}{{2N}}\sum\limits_{k=1}^{N}{\int{\int_{-\infty}^{\infty}{d{\omega_{1}}}}d{\omega_{2}}{f_{0}}^{2}\left({{\omega_{1}},{\omega_{2}}}\right)\cos\left({\left({{\omega_{1}}-{\omega_{2}}}\right)\tau+2\left({2k-N-1}\right)\alpha\tau}\right)}\\\
&=\frac{1}{2}-\frac{1}{2N}\sum\limits_{k=1}^{N}\int\int_{-\infty}^{\infty}{d\omega_{1}}d{\omega_{2}}{f_{0}}^{2}\left(\omega_{1},\omega_{2}\right)(\cos\left(\left(\omega_{1}-\omega_{2}\right)\tau\right)\cos\left(2\left(2k-N-1\right)\alpha\tau\right)\\\
&\quad-\sin\left(\left(\omega_{1}-\omega_{2}\right)\tau\right)\sin\left(2\left(2k-N-1\right)\alpha\tau\right))\\\
&=\frac{1}{2}\left[1-\frac{1}{{N}}\sum\limits_{k=1}^{N}{\cos\left({2\left({2k-N-1}\right)\alpha\tau}\right)\int{\int_{-\infty}^{\infty}{d{\omega_{1}}}}d{\omega_{2}}{f_{0}}^{2}\left({{\omega_{1}},{\omega_{2}}}\right)\cos\left({\left({{\omega_{1}}-{\omega_{2}}}\right)\tau}\right)}\right]\\\
&=\frac{1}{2}\left[1-\frac{1}{{N}}\frac{{\sin(2N\alpha\tau)}}{{\sin(2\alpha\tau)}}\int{\int_{-\infty}^{\infty}{d{\omega_{1}}}}d{\omega_{2}}{f_{0}}^{2}\left({{\omega_{1}},{\omega_{2}}}\right)\cos\left({\left({{\omega_{1}}-{\omega_{2}}}\right)\tau}\right)\right]\\\
&=\frac{1}{2}\left[1-P_{0}\frac{{\sin\left(Nx\right)}}{{\sin\left(x\right)}}\right],\par\end{array}$
(22)

where $x=2\alpha\tau$, which corresponds to the phase spacing caused by two
adjacent spectral modes.
$P_{0}=\frac{1}{{N}}\int{\int_{-\infty}^{\infty}{d{\omega_{1}}}}d{\omega_{2}}{f_{0}}^{2}\left({{\omega_{1}},{\omega_{2}}}\right)\cos\left({\left({{\omega_{1}}-{\omega_{2}}}\right)\tau}\right)$
corresponds to the envelope of the interference patterns. $P_{0}$ can also be
written in the form of a Fourier transform:

$\begin{array}[]{lll}P_{0}&=\frac{1}{N}\int{\int_{-\infty}^{\infty}{d{\omega_{1}}}}d{\omega_{2}}{f_{0}}^{2}\left({{\omega_{1}},{\omega_{2}}}\right)\cos\left({\left({{\omega_{1}}-{\omega_{2}}}\right)\tau}\right)\\\
&=-\frac{1}{2N}\int{\int_{-\infty}^{\infty}{d{\omega_{+}}}}d{\omega_{-}}{f_{0}}^{2}(\frac{1}{2}\left({{\omega_{+}}+{\omega_{-}}}\right),\frac{1}{2}\left({{\omega_{+}}-{\omega_{-}}}\right))\cos\left({{\omega_{-}}\tau}\right)\\\
&=\int_{-\infty}^{\infty}{d{\omega_{-}}}{F_{0}}\left({{\omega_{-}}}\right)\cos\left({{\omega_{-}}\tau}\right)\\\
&={\mathop{\rm
Re}\nolimits}\left({\int_{-\infty}^{\infty}{d{\omega_{-}}}{F_{0}}\left({{\omega_{-}}}\right){e^{-i{\omega_{-}}\tau}}}\right)\\\
&={\mathop{\rm Re}\nolimits}(\mathcal{F}[{F_{0}}({\omega_{-}})]),\end{array}$
(23)

where ${\omega_{+}}={\omega_{1}}+{\omega_{2}}$,
${\omega_{-}}={\omega_{1}}-{\omega_{2}}$,
$F_{0}(\omega_{-})=-\frac{1}{2N}\int_{-\infty}^{\infty}{d{\omega_{+}}}f_{0}^{2}\left({\omega_{+}},{\omega_{-}}\right)$,
and Re denotes the real part.

In this study, we only consider the simplest case; therefore, we assume
$f\left(\omega_{1},\omega_{2}\right)$ as a multi-mode Gaussian function [16,
31]:

$\begin{array}[]{lll}f\left(\omega_{1},\omega_{2}\right)=\sum\limits_{k=1}^{N}\exp\left[-\frac{\left(\omega_{1}-\omega_{0}-\left(2k-N-1\right)\alpha\right)^{2}}{\gamma^{2}}-\frac{\left(\omega_{2}-\omega_{0}+\left(2k-N-1\right)\alpha\right)^{2}}{\gamma^{2}}\right],\end{array}$
(24)

where $\omega_{0}$ is the center frequency and $\gamma$ is the mode width.
Then

$\begin{array}[]{lll}P\left(\tau\right)&=\frac{1}{2}-\frac{1}{2}\iint\nolimits_{-\infty}^{+\infty}{d\omega_{1}d\omega_{2}}\left\\{\sum\limits_{k=1}^{N}\exp{\left[-(\frac{(\omega_{1}-\omega_{0}-(2k-N-1)\alpha)^{2}}{\gamma^{2}}-\frac{(\omega_{2}-\omega_{0}+(2k-N-1)\alpha)^{2}}{\gamma^{2}}\right]}\right\\}^{2}\\\
&\quad\times\cos\left(\left(\omega_{1}-\omega_{2}\right)\tau\right).\end{array}$
(25)

If $\gamma\ll\alpha$, the cross terms can be ignored, then

$\begin{array}[]{lll}P\left(\tau\right)&=\frac{1}{2}-\frac{1}{2}\iint\nolimits_{-\infty}^{+\infty}{d\omega_{1}d\omega_{2}}\sum\limits_{k=1}^{N}\exp\left[-2\frac{(\omega_{1}-\omega_{0}-(2k-N-1)\alpha)^{2}}{\gamma^{2}}-2\frac{(\omega_{2}-\omega_{0}+(2k-N-1)\alpha)^{2}}{\gamma^{2}}\right]\\\
&\quad\times\cos\left(\left(\omega_{1}-\omega_{2}\right)\tau\right)\\\
&=\frac{1}{2}-\frac{1}{2N}\exp\left[-\frac{\gamma^{2}\tau^{2}}{4}\right]\sum\limits_{k=1}^{N}\cos\left(2\left(N+1-2k\right)\alpha\tau\right)\\\
&=\frac{1}{2}-\frac{1}{2N}\exp\left[-\frac{\gamma^{2}\tau^{2}}{4}\right]\frac{\sin\left(2N\alpha\tau\right)}{\sin\left(2\alpha\tau\right)}.\end{array}$
(26)

To understand the omission of the cross terms, we can consider the case of
N=2:

$\begin{array}[]{l}\left[{\exp{\left(-\frac{\left(\omega_{1}-\omega_{0}+\alpha\right)^{2}}{\gamma^{2}}-\frac{\left(\omega_{2}-\omega_{0}+\alpha\right)^{2}}{\gamma^{2}}\right)}}{+\exp{\left(-\frac{\left(\omega_{1}-\omega_{0}-\alpha\right)^{2}}{\gamma^{2}}-\frac{\left(\omega_{2}-\omega_{0}-\alpha\right)^{2}}{\gamma^{2}}\right)}}\right]^{2}\\\
={\exp{\left(-2\frac{\left(\omega_{1}-\omega_{0}+\alpha\right)^{2}}{\gamma^{2}}-2\frac{\left(\omega_{2}-\omega_{0}+\alpha\right)^{2}}{\gamma^{2}}\right)}}{+\exp{\left(-2\frac{\left(\omega_{1}-\omega_{0}-\alpha\right)^{2}}{\gamma^{2}}-2\frac{\left(\omega_{2}-\omega_{0}-\alpha\right)^{2}}{\gamma^{2}}\right)}}\\\
\quad+2\exp{\left(-\frac{\left(\omega_{1}-\omega_{0}+\alpha\right)^{2}}{\gamma^{2}}-\frac{\left(\omega_{2}-\omega_{0}+\alpha\right)^{2}}{\gamma^{2}}-\frac{\left(\omega_{1}-\omega_{0}-\alpha\right)^{2}}{\gamma^{2}}-\frac{\left(\omega_{2}-\omega_{0}-\alpha\right)^{2}}{\gamma^{2}}\right)}.\end{array}$
(27)

The last term is the cross-term. When $\gamma\ll\alpha$, the cross-term is
much smaller than the sum of the first and second terms, so it can be ignored.

## A2: The calculation of multi-slit interference

As shown in Fig. 1(b), the number of slits is N, the separation between
adjacent slits is $d$, and the width of each slit is $a$. The diffraction
angle associated with point $p$ is${\rm{\;}}\theta$. The optical path
difference between two adjacent slits is $d\sin\theta$ and the corresponding
phase difference is $2\pi d\sin\theta/\lambda$. $\lambda$ is the wavelength of
the incident monochromatic light.

Firstly, the light intensity distribution of single-slit diffraction is
calculated according to the Fresnel-Kirchhoff diffraction integral formula.
The light diffracted from one direction is focused on the focal plane of the
lens L at point $p$. The amplitude of single-slit diffraction is

$\begin{array}[]{lll}A_{1}&=C\int_{-\infty}^{\infty}dx{{f_{0}\left(x\right)e^{-ikx\sin\theta}}}=C\int_{-\infty}^{\infty}dx{{f_{0}\left(x\right)e^{-i2\pi
x\frac{{\sin\theta}}{\lambda}}}}=C\mathcal{F}\left[{f_{0}}\left(x\right)\right],\end{array}$
(28)

where $k=\frac{{2\pi}}{\lambda}$, $f_{0}\left(x\right)$ is aperture function,
and $C$ is a constant, which is determined by the power of the light source,
the distance between the slit and the screen, and the size of the slit [21].
Intensity of the light is the magnitude of the Fourier Transform of aperture
function. In this study, we only consider the simplest case. We set aperture
function$f_{0}(x)$ as rectangle function:

$\begin{array}[]{lll}A_{1}&=C\int_{-\frac{a}{2}}^{\frac{a}{2}}{{e^{-ikx\sin\theta}}dx}=\frac{{2C}}{{k\sin\theta}}\sin\left({\frac{{ka\sin\theta}}{2}}\right).\end{array}$
(29)

Let $u=\frac{{\pi a\sin\theta}}{\lambda}$, then

$\begin{array}[]{lll}A_{1}=aC\frac{{\sin u}}{u},\end{array}$ (30)

when $\theta=0$, $u=0,\frac{{\sin u}}{u}=1$, the amplitude due to one slit is
$A_{0}=aC$. So the amplitude of single-slit diffraction is

$\begin{array}[]{lll}A_{1}=A_{0}\frac{{\sin u}}{u}.\end{array}$ (31)

After passing through the first slit, the light field at point $p$ is

$\begin{array}[]{lll}E_{1}=A_{1}\cos\left(\omega
t+\varphi_{0}\right).\end{array}$ (32)

The optical path difference between the two adjacent slits is equal, so the
phase difference is equal. Therefore, the general equation of the light field
at point $p$ is

$\begin{array}[]{lll}E_{i}=A_{1}\cos\left(\omega
t+\varphi_{0}+\left(i-1\right)\delta\right)\quad\left(i=1,2,\cdots
N\right),\par\end{array}$ (33)

where $\delta=\frac{2\pi d\sin\theta}{\lambda}$ is the phase difference
between the two adjacent slits. $i$ is the number of the slit. Therefore, the
combined field at point $p$ is

$\begin{array}[]{lll}E\left(p,t\right)&=\sum\limits_{i=1}^{N}{E_{i}=}A_{1}\sum\limits_{i=1}^{N}{\cos\left[\omega
t+\varphi_{0}+\left(i-1\right)\delta\right]}\\\
&=\frac{{{A_{1}}}}{{2\sin(\frac{\delta}{2})}}\sum\limits_{i=1}^{N}{\cos\left[\omega
t+{\varphi_{0}}+\left(i-1\right)\delta\right]\sin\left(\frac{\delta}{2}\right)}\\\
&=\frac{A_{1}}{2\sin(\frac{\delta}{2})}\sum\limits_{i=1}^{N}\sin\left[\omega
t+\varphi_{0}+\left(i-\frac{1}{2}\right)\delta\right]-\sin\left[\omega
t+\varphi_{0}+\left(i-\frac{3}{2}\right)\delta\right]\\\
&=\frac{A_{1}\sin\left(\frac{N\delta}{2}\right)}{\sin\left(\frac{\delta}{2}\right)}\cos\left[\omega
t+\varphi_{0}+\frac{N-1}{2}\delta\right].\end{array}$ (34)

Finally, the amplitude is

$\begin{array}[]{lll}A_{p}=\frac{A_{1}\sin(\frac{N\delta}{2})}{\sin\left(\frac{\delta}{2}\right)}={A_{0}}\frac{{\sin
u}}{u}\frac{{\sin\left({Nv}\right)}}{{\sin\left(v\right)}},\end{array}$ (35)

where $u=\frac{{\pi a\sin\theta}}{\lambda}$, $v=\frac{{\pi
d\sin\theta}}{\lambda}=\frac{\delta}{2}$. The intensity of the diffraction
pattern is

$\begin{array}[]{lll}I=A_{p}A_{p}^{\ast}=\left(A_{0}\right)^{2}\left(\frac{{\sin}{\left(u\right)}}{u}\right)^{2}\left(\frac{\sin{\left(Nv\right)}}{\sin\left(v\right)}\right)^{2}.\end{array}$
(36)

## A3:The calculation of multi-mode Mach–Zehnder interference

In this section, we consider the interference pattern in a multi-mode
Mach–Zehnder interference, with a setup shown in Fig. 7(a). As calculated in
detail in the supplementary materials of Ref. [30], the coincidence
probability $P_{MZI}\left(\tau\right)$ as a function of optical path delay
$\tau$ can be expressed as

$\begin{array}[]{lll}P_{MZI}\left(\tau\right)=\frac{1}{2}\left[1+\int\nolimits_{-\infty}^{+\infty}{d\omega{{\left|{f\left(\omega\right)}\right|}^{2}}\cos\left({\omega\tau}\right)}\right],\end{array}$
(37)

where $f\left(\omega\right)$ is the spectral amplitude of the laser source.
For simplicity, we have assumed that $f\left(\omega\right)$ is normalized in
the above equation, i.e.,
$\int_{-\infty}^{\infty}{d\omega}|f\left(\omega\right)|^{2}=1$. In multi-mode
Mach-Zehnder interference, $f(\omega)$ can be written as:

$\begin{array}[]{l}f\left({\omega}\right)=\sum\limits_{k=1}^{N}{{f_{0}}\left({{\omega}-{\omega_{0}}-\left({2k-N-1}\right)\alpha}\right)},\\\
\end{array}$ (38)

where $f_{0}\left(\omega\right)$ is an arbitrary distribution function of the
single mode, $N$ is the mode number, $\alpha$ represents the mode spacing, and
$\omega_{0}$ is the mode’s central frequency. If the mode width is much
smaller than the mode spacing, the cross terms can be ignored, then

$\begin{array}[]{lll}P_{MZI}\left(\tau\right)&=\frac{1}{2}+\frac{1}{2}\int\nolimits_{-\infty}^{+\infty}d\omega{\left|{\sum\limits_{k=1}^{N}{{f_{0}}\left({{\omega}-{\omega_{0}}-\left({2k-N-1}\right)\alpha}\right)}}\right|^{2}}\cos\left({\omega\tau}\right)\\\
&=\frac{1}{2}+\frac{1}{2}\int\nolimits_{-\infty}^{+\infty}d\omega{\left|\sum\limits_{k=1}^{N}{{f_{0}}\left(\omega\right)}\right|^{2}}\cos\left({\left(\omega+{\omega_{0}}+\left({2k-N-1}\right)\alpha\right)}\tau\right)\\\
&=\frac{1}{2}\left[1-\sum\limits_{k=1}^{N}{\cos\left(\omega_{0}\tau+{\left({2k-N-1}\right)\alpha\tau}\right)}{\int_{-\infty}^{\infty}{d\omega}}\left|{f_{0}}\left(\omega\right)\right|^{2}\cos\left(\left(\omega\right)\tau\right)\right]\\\
&=\frac{1}{2}\left[1-\frac{1}{{N}}\frac{{\sin\left(N\alpha\tau\right)}}{{\sin\left(\alpha\tau\right)}}\cos{\left(\omega_{0}\tau\right)}{\int_{-\infty}^{\infty}{d{\omega}}}\left|{f_{0}}\left({\omega}\right)\right|^{2}\cos(\omega\tau)\right]\\\
&=\frac{1}{2}\left[1-P_{0}\frac{{\sin\left(Nx\right)}}{{\sin\left(x\right)}}\cos{\left(\omega_{0}\tau\right)}\right],\par\end{array}$
(39)

where $x=\alpha\tau$ and
$P_{0}=\frac{1}{{N}}{\int_{-\infty}^{\infty}{d{\omega}}}\left|{f_{0}}\left({{\omega}}\right)\right|^{2}\cos\left({{\omega}\tau}\right)$
corresponds to the envelope of the interference patterns.

To simplify the analysis, we assume that $f\left(\omega\right)$ is a multi-
mode Gaussian function:

$\begin{array}[]{lll}f\left(\omega\right)=\sum\limits_{k=1}^{N}{\exp\left[{-\frac{{{{\left({\omega-{\omega_{0}}-\left({2k-N-1}\right)\alpha}\right)}^{2}}}}{{{\gamma^{2}}}}}\right]},\end{array}$
(40)

where $\omega_{0}$ is the center frequency and $\alpha$ is the mode spacing.
Then

$\begin{array}[]{lll}P_{MZI}\left(\tau\right)&=\frac{1}{2}+\frac{1}{2}\int\nolimits_{-\infty}^{+\infty}{d\omega{{\left|{f\left(\omega\right)}\right|}^{2}}\cos\left({\omega\tau}\right)}\\\
&=\frac{1}{2}+\frac{1}{2}{\exp\left[{-\frac{{{\gamma^{2}}{\tau^{2}}}}{8}}\right]\sum\limits_{k=1}^{N}{\cos\left({{\omega_{0}}\tau+\left({2k-N-1}\right)\alpha\tau}\right)}}\\\
&=\frac{1}{2}+\frac{1}{{2N}}\exp\left[{-\frac{{{\gamma^{2}}{\tau^{2}}}}{8}}\right]\frac{{\sin\left({N\alpha\tau}\right)}}{{\sin\left({\alpha\tau}\right)}}\cos\left({{\omega_{0}}\tau}\right)\\\
&=\frac{1}{2}+\frac{1}{{2N}}\exp\left[{-\frac{{{\gamma^{2}}{\tau^{2}}}}{8}}\right]\frac{{\sin\left({Nx}\right)}}{{\sin\left({x}\right)}}\cos\left({{\omega_{0}}\tau}\right),\end{array}$
(41)

where $x=\alpha\tau$.

## A4: The calculation of multi-mode NOON-state interference

In this section, we consider the interference pattern in a multi-mode NOON-
state interference, with a setup shown in Fig. 7(b). Here, the NOON-state is a
$(\left|{20}\right\rangle+\left|{02}\right\rangle)/\sqrt{2}$ state, which has
a photon number of 2, but with a spectral-mode number of N, as shown in Fig.
7(e1-e8). As calculated in detail in the supplementary materials of Ref.[30] ,
the coincidence probability $P_{NOON}\left(\tau\right)$ as a function of
optical path delay $\tau$ can be expressed as

$\begin{array}[]{lll}P_{NOON}\left(\tau\right)=\frac{1}{2}+\frac{1}{2}\mathop{\int}\\!\\!\\!\int\nolimits_{-\infty}^{\infty}d{\omega_{1}}d{\omega_{2}}{\left|f\left({{\omega_{1}},{\omega_{2}}}\right)\right|^{2}\cos\left({\omega_{1}}+{\omega_{2}}\right)\tau},\end{array}$
(42)

where $f\left(\omega_{1},\omega_{2}\right)$ is the joint spectral amplitude of
the biphoton. For simplicity, in the preceding equation we has assumed
$f\left(\omega_{1},\omega_{2}\right)$ normalized, i.e.,
$\iint_{-\infty}^{\infty}{d\omega_{1}d\omega_{2}|f\left(\omega_{1},\omega_{2}\right)|^{2}}=1$,
and $f\left(\omega_{1},\omega_{2}\right)$ satisfies the exchanging symmetry of
$f\left(\omega_{1},\omega_{2}\right)=f\left(\omega_{2},\omega_{1}\right)$.

For simplicity, we can further set $f\left(\omega_{1},\omega_{2}\right)$ as
real and normalized, i.e.,
$f\left(\omega_{1},\omega_{2}\right)=f^{*}\left(\omega_{1},\omega_{2}\right)$
and
$\iint_{-\infty}^{\infty}{d\omega_{1}d\omega_{2}\left|f\left(\omega_{2},\omega_{1}\right)\right|^{2}}=1$.
In the multi-mode NOON-state interference ,
$f\left(\omega_{1},\omega_{2}\right)$ can also be written as:

$\begin{array}[]{l}f\left({{\omega_{1}},{\omega_{2}}}\right)=\sum\limits_{k=1}^{N}{{f_{0}}\left({{\omega_{1}}-{\omega_{0}}-\left({2k-N-1}\right)\alpha,{\omega_{2}}-{\omega_{0}}-\left({2k-N-1}\right)\alpha}\right)},\\\
\end{array}$ (43)

where $f_{0}\left({\omega_{1}},{\omega_{2}}\right)$ is an arbitrary
distribution function of the single mode, $N$ is the mode number, $\alpha$
represents the mode spacing, and $\omega_{0}$ is the mode’s central frequency.
If the mode width is much smaller than the mode spacing, the cross terms can
be ignored, then

$\begin{array}[]{lll}P_{NOON}\left(\tau\right)&=\frac{1}{2}+\frac{1}{2}\mathop{\int}\\!\\!\\!\int\nolimits_{-\infty}^{\infty}d{\omega_{1}}d{\omega_{2}}\cos\left(\left({\omega_{1}}+{\omega_{2}}\right)\tau\right)\\\
&\quad\times\left|\sum\limits_{k=1}^{N}f_{0}\left({\omega_{1}}-{\omega_{0}}-\left({2k-N-1}\right)\alpha,{\omega_{2}}-{\omega_{0}}-\left({2k-N-1}\right)\alpha\right)\right|^{2}\\\
&=\frac{1}{2}+\frac{1}{2}\sum\limits_{k=1}^{N}\mathop{\int}\\!\\!\\!\int\nolimits_{-\infty}^{\infty}d{\omega_{1}}d{\omega_{2}}\left|{f_{0}}\left(\omega_{1},\omega_{2}\right)\right|^{2}\\\
&\quad\times\cos\left(\left({\omega_{1}}+{\omega_{2}}+2\omega_{0}+2\left({2k-N-1}\right)\alpha\right)\tau\right)\\\
&=\frac{1}{2}+\frac{1}{{2N}}\sum\limits_{k=1}^{N}{\cos\left({2\tau\left({{\omega_{0}}+(2k-N-1)\alpha}\right)}\right)}\\\
&\quad\times\int\\!\\!\\!\int\nolimits_{-\infty}^{\infty}d{\omega_{1}}d{\omega_{2}}\left|{f_{0}}\left(\omega_{1},\omega_{2}\right)\right|^{2}\cos\left(\omega_{1}+\omega_{2}\right)\\\
&=\frac{1}{2}+\frac{1}{{2N}}\frac{{\sin\left({Nx}\right)}}{{\sin\left({x}\right)}}\cos\left({2{\omega_{0}}\tau}\right)\int\\!\\!\\!\int\nolimits_{-\infty}^{\infty}d{\omega_{1}}d{\omega_{2}}\left|{f_{0}}\left(\omega_{1},\omega_{2}\right)\right|^{2}\cos\left(\omega_{1}+\omega_{2}\right)\\\
&=\frac{1}{2}+\frac{1}{{2}}P_{0}\frac{{\sin\left({Nx}\right)}}{{\sin\left({x}\right)}}\cos\left({2{\omega_{0}}\tau}\right),\end{array}$
(44)

where $x=2\alpha\tau$ and
$P_{0}=\frac{1}{{N}}\int{\int_{-\infty}^{\infty}{d{\omega_{1}}}}d{\omega_{2}}\left|{f_{0}}\left({{\omega_{1}},{\omega_{2}}}\right)\right|^{2}\cos\left({\left({{\omega_{1}}+{\omega_{2}}}\right)\tau}\right)$
corresponds to the envelope of the interference patterns. For simplicity, we
also assume $f\left(\omega_{1},\omega_{2}\right)$ as a multi-mode Gaussian
function:

$\begin{array}[]{lll}f\left(\omega_{1},\omega_{2}\right)=\sum\limits_{k=1}^{N}\exp\left[-\frac{\left(\omega_{1}-\omega_{0}-\left(2k-N-1\right)\alpha\right)^{2}}{\gamma^{2}}-\frac{\left(\omega_{2}-\omega_{0}+\left(2k-N-1\right)\alpha\right)^{2}}{\gamma^{2}}\right],\end{array}$
(45)

where $\omega_{0}$ is the center frequency and $\alpha$ is the mode
separation. Then,

$\begin{array}[]{lll}P_{NOON}\left(\tau\right)&=\frac{1}{2}+\frac{1}{2}\mathop{\int}\\!\\!\\!\int\nolimits_{-\infty}^{\infty}d{\omega_{1}}d{\omega_{2}}\cos(({\omega_{1}}+{\omega_{2}})\tau)\\\
&\quad\times\sum\limits_{k=1}^{N}{\exp}\left[-2\frac{{{{\left({\omega_{1}}-{\omega_{0}}-\left(2k-N-1\right)\alpha\right)}^{2}}}}{{{\gamma^{2}}}}-2\frac{{{{\left({\omega_{2}}-{\omega_{0}}-\left(2k-N-1\right)\alpha\right)}^{2}}}}{{{\gamma^{2}}}}\right]\\\
&=\frac{1}{2}+\frac{1}{{2N}}\exp\left[-\frac{{{\gamma^{2}}{\tau^{2}}}}{4}\right]\sum\limits_{k=1}^{N}{\cos\left({2\tau\left({{\omega_{0}}+(2k-N-1)\alpha}\right)}\right)}\\\
&=\frac{1}{2}+\frac{1}{{2N}}\exp\left[-\frac{{{\gamma^{2}}{\tau^{2}}}}{4}\right]\frac{{\sin\left({2N\alpha\tau}\right)}}{{\sin\left({2\alpha\tau}\right)}}\cos\left({2{\omega_{0}}\tau}\right)\\\
&=\frac{1}{2}+\frac{1}{{2N}}\exp\left[-\frac{{{\gamma^{2}}{\tau^{2}}}}{4}\right]\frac{{\sin\left({Nx}\right)}}{{\sin\left({x}\right)}}\cos\left({2{\omega_{0}}\tau}\right),\end{array}$
(46)

where $x=2\alpha\tau$, which determines the phase spacing caused by two
adjacent spectral modes.

## Funding

This work was supported by the National Natural Science Foundation of China
(Grant Numbers 92365106, 12074299, and 11704290) and the Natural Science
Foundation of Hubei Province (2022CFA039).

## Disclosures

The authors declare no conflicts of interest.

## Data Availability

Data underlying the results presented in this paper are not publicly available
at this time but may be obtained from the authors upon reasonable request.

## References

  * [1] C. K. Hong, Z. Y. Ou, and L. Mandel, “Measurement of subpicosecond time intervals between two photons by interference,” Phys. Rev. Lett. 59, 2044–2046 (1987).
  * [2] A. M. Brańczyk, “Hong-Ou-Mandel interference,” arXiv:1711.00080 (2017).
  * [3] F. Bouchard, A. Sit, Y. Zhang, R. Fickler, F. M. Miatto, Y. Yao, F. Sciarrino, and E. Karimi, “Two-photon interference: the Hong-Ou-Mandel effect,” Rep. Prog. Phys. 84, 012402 (2020).
  * [4] Y. Liu, R. Quan, X. Xiang, H. Hong, M. Cao, T. Liu, R. Dong, and S. Zhang, “Quantum clock synchronization over 20-km multiple segmented fibers with frequency-correlated photon pairs and HOM interference,” Appl. Phys. Lett. 119, 144003 (2021).
  * [5] C. Yang, S.-J. Niu, Z.-Y. Zhou, Y. Li, Y.-H. Li, Z. Ge, M.-Y. Gao, Z.-Q.-Z. Han, R.-H. Chen, G.-C. Guo, and B.-S. Shi, “Advantages of the frequency-conversion technique in quantum interference,” Phys. Rev. Appl. 105, 063715 (2022).
  * [6] R.-B. Jin, R. Shimizu, M. Fujiwara, M. Takeoka, R. Wakabayashi, T. Yamashita, S. Miki, H. Terai, T. Gerrits, and M. Sasaki, “Simple method of generating and distributing frequency-entangled qudits,” Quantum Sci. Technol. 1, 015004 (2016).
  * [7] D. H. Useche, A. Giraldo-Carvajal, H. M. Zuluaga-Bucheli, J. A. Jaramillo-Villegas, and F. A. González, “Quantum measurement classification with qudits,” Quantum Inform. Process. 21 (2021).
  * [8] A. Castro, A. García Carrizo, S. Roca, D. Zueco, and F. Luis, “Optimal control of molecular spin qudits,” Phys. Rev. Appl. 17, 064028 (2022).
  * [9] Z.-X. Yang, Z.-Q. Zeng, Y. Tian, S. Wang, R. Shimizu, H.-Y. Wu, S. Liu, and R.-B. Jin, “Spatial–spectral mapping to prepare frequency entangled qudits,” Opt. Lett. 48, 2361–2364 (2023).
  * [10] G. Y. Xiang, H. F. Hofmann, and G. J. Pryde, “Optimal multi-photon phase sensing with a single interference fringe,” Sci. Rep. 3, 2684–2684 (2013).
  * [11] R.-B. Jin, M. Fujiwara, R. Shimizu, R. J. Collins, G. S. Buller, T. Yamashita, S. Miki, H. Terai, M. Takeoka, and M. Sasaki, “Detection-dependent six-photon Holland-Burnett state interference,” Sci. Rep. 6, 36914 (2016).
  * [12] A. Lyons, C. G. Knee, E. Bolduc, T. Roger, J. Leach, M. E. Gauger, and D. Faccio, “Attosecond-resolution Hong-Ou-Mandel interferometry,” Sci. Adv. 4, eaap9416 (2018).
  * [13] N. B. Lingaraju, H.-H. Lu, S. Seshadri, P. Imany, D. E. Leaird, J. M. Lukens, and A. M. Weiner, “Quantum frequency combs and Hong-Ou-Mandel interferometry: the role of spectral phase coherence,” Opt. Express 27, 38683–38697 (2019).
  * [14] Y. Chen, M. Fink, F. Steinlechner, J. P. Torres, and R. Ursin, “Hong-Ou-Mandel interferometry on a biphoton beat note,” npj Quantum Inform. 5, 43 (2019).
  * [15] Y. Chen, S. Ecker, L. Chen, F. Steinlechner, M. Huber, and R. Ursin, “Temporal distinguishability in Hong-Ou-Mandel interference for harnessing high-dimensional frequency entanglement,” npj Quantum Inform. 7, 167 (2021).
  * [16] C. L. Morrison, F. Graffitti, P. Barrow, A. Pickston, J. Ho, and A. Fedrizzi, “Frequency-bin entanglement from domain-engineered down-conversion,” APL Photon. 7, 066102 (2022).
  * [17] R. Xue, X. Yao, X. Liu, H. Wang, H. Li, Z. Wang, L. You, Y. Huang, and W. Zhang, “Spatial quantum beating of adjustable biphoton frequency comb with high-dimensional frequency-bin entanglement,” IEEE Photon. J. 11, 1–9 (2019).
  * [18] N. Fabre, G. Maltese, F. Appas, S. Felicetti, A. Ketterer, A. Keller, T. Coudreau, F. Baboux, M. I. Amanti, S. Ducci, and P. Milman, “Generation of a time-frequency grid state with integrated biphoton frequency combs,” Phys. Rev. A 102, 012607 (2020).
  * [19] Z. Xie, T. Zhong, S. Shrestha, X. Xu, J. Liang, Y.-X. Gong, J. C. Bienfang, A. Restelli, J. H. Shapiro, F. N. C. Wong, and C. W. Wong, “Harnessing high-dimensional hyperentanglement through a biphoton frequency comb,” Nat. Photon. 9, 536–542 (2015).
  * [20] K.-C. Chang, X. Cheng, M. C. Sarihan, A. K. Vinod, Y. S. Lee, T. Zhong, Y.-X. Gong, Z. Xie, J. H. Shapiro, F. N. C. Wong, and C. W. Wong, “648 hilbert-space dimensionality in a biphoton frequency comb: entanglement of formation and schmidt mode decomposition,” npj Quantum Inform. 7 (2021).
  * [21] M. Born and E. Wolf, _Principles of Optics, 6-th ed_ (Cambridge University, 1980).
  * [22] T. Young, “A course of lectures on natural philosophy and the mechanical arts,” Lecture 39 1, 463–464 (1807).
  * [23] P. Hariharan, _Optical interferometry_ (Academic, Amsterdam Boston, 2003).
  * [24] J. W. Jewett and R. Serway, _Physics for Scientists and Engineers with Modern physics_ (Pearson Education, Upper Saddle River, N.J, 2008).
  * [25] H. D. Young, R. A. Freedman, and A. L. Ford, _Sears and Zemansky’s University Physics with Modern Physics, 13th Edition_ (Addison-Wesley, Boston, 2012).
  * [26] A. B. U’Ren, R. K. Erdmann, M. de la Cruz-Gutierrez, and I. A. Walmsley, “Generation of two-photon states with an arbitrary degree of entanglement via nonlinear crystal superlattices,” Phys. Rev. Lett. 97, 223602 (2006).
  * [27] P. J. Mosley, J. S. Lundeen, B. J. Smith, P. Wasylczyk, A. B. U’Ren, C. Silberhorn, and I. A. Walmsley, “Heralded generation of ultrafast single photons in pure quantum states,” Phys. Rev. Lett. 100, 133601 (2008).
  * [28] B. Li, B. Yuan, C. Chen, X. Xiang, R. Quan, R. Dong, S. Zhang, and R.-B. Jin, “Spectrally resolved two-photon interference in a modified Hong–Ou–Mandel interferometer,” Optics & Laser Technology 159, 109039 (2023).
  * [29] W. P. Grice and I. A. Walmsley, “Spectral information and distinguishability in type-II down-conversion with a broadband pump,” Phys. Rev. A 56, 1627–1634 (1997).
  * [30] R.-B. Jin and R. Shimizu, “Extended Wiener-Khinchin theorem for quantum spectral analysis,” Optica 5, 93–98 (2018).
  * [31] J.-L. Zhu, W.-X. Zhu, X.-T. Shi, C.-T. Zhang, X. Hao, Z.-X. Yang, and R.-B. Jin, “Design of mid-infrared entangled photon sources using lithium niobate,” J. Opt. Soc. Am. B 40, A9 (2023).
  * [32] H. Cramér, _Mathematical methods of statistics_ , vol. 26 (Princeton University, 1999).
  * [33] R.-B. Jin, R. Shimizu, T. Ono, M. Fujiwara, G.-W. Deng, Q. Zhou, M. Sasaki, and M. Takeoka, “Spectrally resolved NOON state interference,” arXiv: 2104.01062 (2021).