Amit Saha

Cisco Systems (United States)

Author Statistics

Papers

Citation

H-Index

i-10 index

Research Trends

Author Order

Document Type

Co-Authors

Amlan Chakrabarti

University of Calcutta

David B. Johnson

Los Alamos National Laboratory

Santashil PalChaudhuri

Rice University

Johnu George

Nutanix (United States)

Tapabrata Ray

UNSW Sydney

Susmita Sur‐Kolay

Indian Statistical Institute

Kalyanmoy Deb

Michigan State University

Xinyuan Huang

Tianjin Medical University Eye Hospital

Debo Dutta

Nutanix (United States)

Debasri Saha

University of Calcutta

Cooperative Institutions

Rice University

University of Calcutta

Cisco Systems (United States)

UNSW Sydney

Indian Statistical Institute

National Institute of Technology Durgapur

Indian Institute of Engineering Science and Technology, Shibpur

Ahsanullah University of Science and Technology

Indian Agricultural Statistics Research Institute

Google (United States)

Author Statistics

Papers

Citation

H-Index

i-10 index

Research Field

Intermediate-qudit assisted Improved quantum algorithm for string matching with an Advanced Decomposition of Fredkin gate

arXiv (Cornell University) (2023)

Amit Saha Om Khanna

The circuit-level implementation of a quantum string-matching algorithm, which matches a search string (pattern) of length $M$ inside a longer text of length $N$, has already been demonstrated in the literature to outperform its classical counterparts in terms of time complexity and space complexity. Higher-dimensional quantum computing is becoming more and more common as a result of its powerful storage and processing capabilities. In this article, we have shown an improved quantum circuit implementation for the string-matching problem with the help of higher-dimensional intermediate temporary qudits. It is also shown that with the help of intermediate qudits not only the complexity of depth can be reduced but also query complexity can be reduced for a quantum algorithm, for the first time to the best of our knowledge. Our algorithm has an improved query complexity of $O(\sqrt{N-M+1})$ with overall time complexity $O\left(\sqrt{N-M+1}\left((\log {(N-M+1)} \log N)+\log (M)\right)\right)$ as compared to the state-of-the-art work which has a query complexity of $O(\sqrt{N})$ with overall time complexity $O\left(\sqrt{N}\left((\log N)^{2}+\log (M)\right)\right)$, while the ancilla count also reduces to $\frac{N}{2}$ from $\frac{N}{2}+M$. The cost of state-of-the-art quantum circuit for string-matching problem is colossal due to a huge number of Fredkin gates and multi-controlled Toffoli gates. We have exhibited an improved gate cost and depth over the circuit by applying a proposed Fredkin gate decomposition with intermediate qutrits (3-dimensional qudits or ternary systems) and already existing logarithmic-depth decomposition of $n$-qubit Toffoli or multi-controlled Toffoli gate (MCT) with intermediate ququarts (4-dimensional qudits or quaternary systems). We have also asserted that the quantum circuit cost is relevant instead of using higher dimensional qudits through error analysis.

Circuit complexity

Quantum circuit

Toffoli gate

Gate count

10.48550/arxiv.2304.03050

Cite

Citations (1)

Conferences - Mobile computing at the beach

IEEE Pervasive Computing (2004)

Justin Mazzola Paluska A. Mark Dalton Prasad Boddupalli Amit Saha Αναστάσιος Παπαθανασίου

The Fifth IEEE Workshop on Mobile Computing Systems and Applications descended on the Beach Resort in Monterey, California, for a series of technical discussions of new research in pervasive and mobile computing.

Context-aware pervasive systems

End-user computing

10.1109/mprv.2004.1269137

Cite

Citations (1)

A Bi-criterion Approach to Multimodal Optimization: Self-adaptive Approach

Lecture notes in computer science (2010)

Amit Saha Kalyanmoy Deb

10.1007/978-3-642-17298-4_10

Cite

Citations (13)

A generic simple model of synaptic memristor with local activity for neuromorphic applications

Journal of Computational Electronics (2023)

Nune Pratyusha Santanu Mandal Amit Saha Rajesh Saha

Memristor

Neuromorphic engineering

Synaptic weight

10.1007/s10825-023-02007-x

Cite

Citations (2)

Search of clustered marked states with lackadaisical quantum walks

arXiv (Cornell University) (2018)

Amit Saha Ritajit Majumdar Debasri Saha Amlan Chakrabarti Susmita Sur‐Kolay

Nature of quantum walk in presence of multiple marked state has been studied by Nahimovs and Rivosh \cite{10.1007/978-3-662-49192-8_31}. They have shown that if the marked states are arranged in a $\sqrt{k} \times \sqrt{k}$ cluster in a $\sqrt{N} \times \sqrt{N}$ grid, then to find a single marked state among the multiple ones, quantum walk requires $\Omega(\sqrt{N} - \sqrt{k})$ time. In this paper, we show that using lackadaisical quantum walk with the weight of the self-loop as $\frac{4}{N(k + \lfloor{\frac{\sqrt{{k}}}{2}}\rfloor)}$, where $k$ is odd, the probability of finding a marked state increases by $\sim 0.2$. Furthermore, we show that instead of applying the quantum walk $\mathcal{O}(k)$ times to find all the marked states, classical search in the vicinity of the marked state found after the first implementation of the quantum walk can find all the marked states in $\mathcal{O}(\sqrt{k})$ time on average.

Quantum walk

10.48550/arxiv.1804.01446

Cite

Citations (6)

Tiered Object Storage using Persistent Memory.

arXiv (Cornell University) (2018)

Johnu George Ramdoot Pydipaty Xinyuan Huang Amit Saha Debo Dutta

Most data intensive applications often access only a few fields of the objects they are operating on. Since NVM provides fast, byte-addressable access to durable memory, it is possible to access various fields of an object stored in NVM directly without incurring any serialization and deserialization cost. This paper proposes a novel tiered object storage model that modifies a data structure such that only a chosen subset of fields of the data structure are stored in NVM, while the remaining fields are stored in a cheaper (and a traditional) storage layer such as HDDs/SSDs. We introduce a novel linear-programming based optimization framework for deciding the field placement. Our proof of concept demonstrates that a tiered object storage model improves the execution time of standard operations by up to 50\% by avoiding the cost of serialization/deserialization and by reducing the memory footprint of operations.

Serialization

Object storage

Memory footprint

Persistent data structure

Data access

Source

Cite

Citations (0)

A Scalable and Cloud-Native Hyperparameter Tuning System.

arXiv (Cornell University) (2020)

Johnu George Ce Gao Richard Liu Hou Gang Liu Yuan Yan Tang

In this paper, we introduce Katib: a scalable, cloud-native, and production-ready hyperparameter tuning system that is agnostic of the underlying machine learning framework. Though there are multiple hyperparameter tuning systems available, this is the first one that caters to the needs of both users and administrators of the system. We present the motivation and design of the system and contrast it with existing hyperparameter tuning systems, especially in terms of multi-tenancy, scalability, fault-tolerance, and extensibility. It can be deployed on local machines, or hosted as a service in on-premise data centers, or in private/public clouds. We demonstrate the advantage of our system using experimental results as well as real-world, production use cases. Katib has active contributors from multiple companies and is open-sourced at \emph{this https URL} under the Apache 2.0 license.

Hyperparameter

Extensibility

NoSQL

Source

Cite

Citations (1)

Adaptive clock synchronization in sensor networks

Santashil PalChaudhuri Amit Saha David B. Johnson

Recent advances in technology have made low cost, low power wireless sensors a reality. Clock synchronization is an important service in any distributed system, including sensor network systems. Applications of clock synchronization in sensor networks include data integration in sensors, sensor reading fusion, TDMA medium access scheduling, and power mode energy saving. However, for a number of reasons, standard clock synchronization protocols are unsuitable for direct application in sensor networks. In this paper, we introduce the concept of adaptive clock synchronization based on the need of the application and the resource constraint in the sensor networks. We describe a probabilistic method for clock synchronization that uses the higher precision of receiver-to-receiver synchronization, as described in Reference Broadcast Synchronization (RBS) protocol. This deterministic protocol is extended to provide a probabilistic bound on the accuracy of the clock synchronization, allowing for a tradeo between accuracy and resource requirement. Expressions to convert service specifications (maximum clock synchronization error and confidence probability) to actual protocol parameters (minimum number of messages and synchronization overhead) are derived. Further, we extend this protocol for maintaining clock synchronization in a multihop network.

Self-clocking signal

Data synchronization

Clock drift

Digital clock manager

10.1145/984622.984672

Cite

Citations (175)

On Using Non-Volatile Memory in Apache Lucene

arXiv (Cornell University) (2018)

Ramdoot Pydipaty Amit Saha

Apache Lucene is a widely popular information retrieval library used to provide search functionality in an extremely wide variety of applications. Naturally, it has to efficiently index and search large number of documents. With non-volatile memory in DIMM form factor (NVDIMM), software now has access to durable, byte-addressable memory with write latency within an order of magnitude of DRAM write latency. In this preliminary article, we present the first reported work on the impact of using NVDIMM on the performance of committing, searching, and near-real time searching in Apache Lucene. We show modest improvements by using NVM but, our empirical study suggests that bigger impact requires redesigning Lucene to access NVM as byte-addressable memory using loads and stores, instead of accessing NVM via the file system.

10.48550/arxiv.1804.04343

Cite

Citations (0)

Probabilistic Clock Synchronization Service in Sensor Networks

David B. Johnson Santashil PalChaudhuri Amit Saha

Source

Cite

Citations (26)