检索结果-内蒙古大学图书馆

Asymptotically improved circuit for a d-ary Grover's algorithm with advanced decomposition of the n-qudit Toffoli gate

学校读者我要写书评

暂无评论

Physical Review A 2022年第6期105卷 062453-062453页

作者： Amit Saha Ritajit Majumdar Debasri Saha Amlan Chakrabarti Susmita Sur-Kolay A. K. Choudhury School of Information Technology University of Calcutta Calcutta 700106 India ATOS Pune 411045 India Advanced Computing & Microelectronics Unit Indian Statistical Institute Calcutta 700108 India

The progress in building quantum computers to execute quantum algorithms has recently been remarkable. Grover's search algorithm in a binary quantum system provides a considerable speed-up over the classical paradigm. It can be extended to a d-ary (qudit) quantum system also for utilizing the advantage of larger state space, which helps to reduce the runtime of the algorithm as compared to the traditional binary quantum systems. In a qudit quantum system, an n-qudit Toffoli gate plays a significant role in the accurate implementation of Grover's algorithm. In this article, a generalized n-qudit Toffoli gate is realized using higher-dimensional qudits to attain a logarithmic depth decomposition without ancilla qudit. The circuit for Grover's algorithm has then been designed for any d-ary quantum system, where d≥2, with the proposed n-qudit Toffoli gate to obtain optimized depth compared to earlier approaches. The technique for decomposing an n-qudit Toffoli gate requires access to two immediately higher-energy levels, making the design susceptible to errors. Nevertheless, we show that the percentage decrease in the probability of error is significant with both gate count and circuit depth reduced as compared to that in state-of-the-art works.

关键词： Quantum computation Quantum engineering

Improved bounds on the span of L(1, 2)-edge labeling of some infinite regular grids

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Bandopadhyay, Susobhan Ghosh, Sasthi C. Koley, Subhasis School Of Computer Sciences National Institute Of Science Education And Research Bhubaneswar India Advanced Computing And Microelectronics Unit Indian Statistical Institute Kolkata India

For two given nonnegative integers h and k, an L(h, k)-edge labeling of a graph G is the assignment of labels {0, 1,⋯, n} to the edges so that two edges having a common vertex are labeled with difference at least h and two edges not having any common vertex but having a common edge connecting them are labeled with difference at least k. The span λ′h,k(G) is the minimum n such that G admits an L(h, k)-edge labeling. Here our main focus is on finding λ′1,2(G) for L(1, 2)-edge labeling of infinite regular hexagonal (T3), square (T4), triangular (T6) and octagonal (T8) grids. It was known that 7 ≤ λ′1,2(T3) ≤ 8, 10 ≤ λ′1,2(T4) ≤ 11, 16 ≤ λ′1,2(T6) ≤ 20 and 25 ≤ λ′1,2(T8) ≤ 28. Here we settle two long standing open questions i.e. λ′1,2(T3) and λ′1,2(T4). We show λ′1,2(T3) = 7, λ′1,2(T4) = 11. We also improve the bound for T6and T8and prove λ′1,2(T6) ≥ 18, λ′1,2(T8) ≥ 26. © 2022, CC BY.

关键词： Graph theory

SOK: An Evaluation of Quantum Authentication through Systematic Literature Review

学校读者我要写书评

暂无评论

SSRN

SSRN 2021年

作者： Majumdar, Ritajit Das, Sanchari Advanced Computing and Microelectronics Unit Indian Statistical Institute Kolkata India University of Denver

Quantum computers are considered a blessing to the dynamic technological world that promises to solve complex problems much faster than their known classical counterparts. Such computational power imposes critical threats on modern cryptography where it has been proven that asymmetric key cryptosystem will be rendered useless in a quantum world. However, we can utilize such a powerful mechanism for improving computer security by implementing such technology to solve complex data security problems such as authentication, secrets management, and others. Mainly, Quantum Authentication (QA) is an emerging concept in computer security that creates robust authentication for organizations, systems, and individuals. To delve deeper into the concept, for this research, we have further investigated QA through a detailed systematic literature review done on a corpus of N = 859 papers. We briefly discuss the major protocols used by various papers to achieve QA, and also note the distribution of papers using those protocols. We analyzed the technological limitations mentioned by previous researchers and highlighted the lack of human-centered solutions for such modern inventions. We emphasize the importance of research in the user aspect of QA to make the users aware of its potential advantages and disadvantages as we move to the quantum age. © 2021, The Authors. All rights reserved.

关键词： Authentication

On Fault Tolerance of Circuits with Intermediate Qutrit-assisted Gate Decomposition

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Majumdar, Ritajit A., Saha A., Chakrabarti S., Sur-Kolay Advanced Computing & Microelectronics Unit Indian Statistical Institute India Atos Pune India A. K. Choudhury School of Information Technology University of Calcutta India

The use of a few intermediate qutrits for efficient decomposition of 3-qubit unitary gates has been proposed, to obtain an exponential reduction in the depth of the decomposed circuit. An intermediate qutrit implies that a qubit is operated as a qutrit in a particular execution cycle. This method, primarily for the NISQ era, treats a qubit as a qutrit only for the duration when it requires access to the state |2〉 during the computation. In this article, we study the challenges of including fault-tolerance in such a decomposition. We first show that any qubit that requires access to the state |2〉 at any point in the circuit, must be encoded using a qutrit quantum error correcting code (QECC), thus resulting in a circuit with both qubits and qutrits at the outset. Since qutrits are noisier than qubits, the former is expected to require higher levels of concatenation to achieve a particular accuracy than that for qubit-only decomposition. Next, we derive analytically (i) the number of levels of concatenation required for qubit-qutrit and qubit-only decompositions as a function of the probability of error, and (ii) the criterion for which qubit-qutrit decomposition leads to a lower gate count than qubit-only decomposition. We present numerical results for these two types of decomposition and obtain the situation where qubit-qutrit decomposition excels for the example circuit of the quantum adder by considering different values for quantum hardware-noise and non-transversal implementation of the 2-controlled ternary CNOT gate. © 2022, CC BY.

关键词： Timing circuits

Approximate Shortest Paths in Polygons with Violations

学校读者我要写书评

暂无评论

International Journal of Computational Geometry and Applications 2020年第1期30卷 79-95页

作者： Dutta, Binayak Roy, Sasanka Department of Computer Science and Engineering Tezpur University Tezpur India Advanced Computing and Microelectronics Unit Indian Statistical Institute Kolkata India

We study the shortest k-violation path problem in a simple polygon. Let P be a simple polygon in 2 with n vertices and let s,t be a pair of points in P. Let int(P) represent the interior of P. Let P = 2(P) represent the exterior of P. For an integer k ≥ 0, the shortest k-violation path problem in P is the problem of computing the shortest path from s to t in P, such that at most k path segments are allowed to be in P. The subpaths of a k-violation path are not allowed to bend in P. For any k, we present a (1 + 2) factor approximation algorithm for the problem that runs in O(n2σ2klog n2σ2 + n2σ2k) time. Here σ = O(log(L r)) and, L, r are geometric parameters. © 2020 World Scientific Publishing Company.

关键词： approximation polygons shortest paths Steiner points triangulation violations

Depth optimized ansatz circuit in QAOA for Max-Cut

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Majumdar, Ritajit Bhoumik, Debasmita Madan, Dhiraj Vinayagamurthy, Dhinakaran Raghunathan, Shesha Sur-Kolay, Susmita Advanced Computing & Microelectronics Unit Indian Statistical Institute IBM Research India IBM Systems India

While a Quantum Approximate Optimization Algorithm (QAOA) is intended to provide a quantum advantage in finding approximate solutions to combinatorial optimization problems, noise in the system is a hurdle in exploiting its full potential. Several error mitigation techniques have been studied to lessen the effect of noise on this algorithm. Recently, Majumdar et al. proposed a Depth First Search (DFS) based method to reduce n-1 CNOT gates in the ansatz design of QAOA for finding Max-Cut in a graph G = (V;E), jV j = n. However, this method tends to increase the depth of the circuit, making it more prone to relaxation error. The depth of the circuit is proportional to the height of the DFS tree, which can be n-1 in the worst case. In this paper, we propose an O(Δ · n2) greedy heuristic algorithm, where Δ is the maximum degree of the graph, that finds a spanning tree of lower height, thus reducing the overall depth of the circuit while still retaining the n-1 reduction in the number of CNOT gates needed in the ansatz. We numerically show that this algorithm achieves 10 times increase in the probability of success for each iteration of QAOA for Max-Cut. We further show that although the average depth of the circuit produced by this heuristic algorithm still grows linearly with n, our algorithm reduces the slope of the linear increase from 1 to 0:11. © 2021, CC BY.

关键词： Heuristic algorithms

A Multi-Arm-Bandit Based Resource Block Allocation in RIS Assisted Wireless Network

学校读者我要写书评

暂无评论

A Multi-Arm-Bandit Based Resource Block Allocation in RIS As...

IEEE International Symposium on Network computing and Applications

作者： Souvik Deb Shankar Kumar Ghosh Sasthi C. Ghosh Advanced Computing & Microelectronics Unit Indian Statistical Institute Kolkata India Presidency University Bangalore India

ISBN: (纸本)9781665495516

Designing resource block (RB) allocation mechanism for reconfigurable intelligent surface (RIS) assisted wireless networks is quite limited in the preceding literature. In RI S assisted environment, a user equipment (UE) receives throughput through two channels: firstly, through the direct channel from base station (BS) to UE; secondly, through the indirect channel from BS to UE via the RIS. The existing RB allocation mechanism considers only the direct channel conditions. However, in RIS assisted environment, RB selection based on only direct channel condition may not be the optimal one. This is because, a distant UE can achieve a high throughput through the indirect channel even if the direct channel condition is not good. In this work, first, we formulate the RB allocation problem in RIS assisted environment as a multi arm bandit (MAB) problem. Then based on the MAB formulation, we develop a two-phase $\epsilon$ -greedy algorithm which explicitly considers the throughput achievable through the indirect channel while selecting RBs. In exploitation phase, it selects the RB providing maximum reward with a probability $1-\epsilon$ . In exploration phase, any available RB is selected randomly with a probability $\epsilon$ . Finally, through extensive system level simulations, we have shown that our proposed algorithm performs better than an existing proportional fairness based RB allocation mechanism in terms of call dropping probability and system throughput.

关键词： Base stations Wireless networks Reconfigurable intelligent surfaces Throughput Resource management

Anomaly Detection in Evolutionary Social Networks leveraging Community Structure

学校读者我要写书评

暂无评论

Anomaly Detection in Evolutionary Social Networks leveraging...

IEEE International Conference on Service Operations and Logistics, and Informatics, SOLI

作者： Arnab Kumar Ghoshal Nabanita Das Asutosh College Kolkata India Advanced Computing and Microelectronics Unit Indian Statistical Institute Kolkata India

ISBN: (纸本)9781665467230

Social networks are temporally evolving by nature and in general, the evolution takes place gradually with time. But occasionally, the nodes may exhibit anomalous behavior that is to be detected and reported in real time. Usually, the social networks are represented as a temporal stream of weighted graphs, where edge weights stand for frequency or power of actions. Here, for identification of anomalies in evolutionary social networks, we follow an action based approach leveraging the community structure of the network, where it is shown that only the Community Boundary Nodes are enough to detect anomaly in a temporally evolving social network. We introduce a new definition of anomaly score for nodes based on its action history. To the best of our knowledge, this is the first work to exploit the community boundary nodes of an evolutionary social network to identify the graph snapshots containing anomalous events. Experimental studies on real-world as well as synthetic evolutionary networks show that the proposed technique achieves almost 13% improvement in F-Score compared to the state-of-the-art algorithms. Moreover, parallel implementation of the proposed technique results nearly 6 x speedup making it suitable for real time computation of anomaly in evolutionary social networks.

关键词： Knowledge engineering Social networking (online) Image edge detection Conferences Real-time systems History Informatics

Optimizing Ansatz design in QAOA for max-cut

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Majumdar, Ritajit Madan, Dhiraj Bhoumik, Debasmita Vinayagamurthy, Dhinakaran Raghunathan, Shesha Sur-Kolay, Susmita Advanced Computing & Microelectronics Unit Indian Statistical Institute IBM Research India IBM Systems India

Quantum Approximate Optimization Algorithm (QAOA) has been studied widely in the literature, primarily for finding an approximate value of the maximum cut size of a graph. QAOA is composed of a problem hamiltonian and a mixer hamiltonian which are applied alternately for p ≥ 1 layers. The circuit for this algorithm requires 2m CNOT gates in each layer, where m is the number of edges in the graph. CNOT gate is one of the primary sources of error in modern quantum computers. In this paper, we propose two techniques for reducing the number of CNOT gates in the circuit which are independent of the hardware architecture. For a graph with n vertices, we first propose a technique based on edge coloring that can reduce upto bn2 c CNOT gates in the circuit. Next, we propose another technique based on Depth First Search (DFS) that can reduce n − 1 CNOT gates at the cost of some increased depth. We analytically derive the criteria for which the reduction in the number of CNOT gates due to the DFS based technique can provide lower error probability even with some increased depth, and show that all graphs conform to this criteria, making this technique universal. We further show that this proposed optimization holds even in the post transpilation stage of the circuit, which is actually executed in the IBM Quantum hardware [1]. We simulate these two techniques for graphs of various sparsity with the ibmq_manhattan noise model and show that the DFS based technique outperforms the edge coloring based technique, which in turn, outperforms the traditional QAOA circuit in terms of reduction in the number of CNOT gates, and hence the probability of error of the circuit. © 2021, CC BY.

关键词： Hamiltonians