Search

Rapid development in quantum computing leads to the appearance of several quantum applications. Quantum Fourier Transformation (QFT) sits at the heart of many of these applications. Existing work leverages SAT solver or heuristics to generate a hardware-compliant circuit for QFT by inserting SWAP gates to remap logical qubits to physical qubits. However, they might face problems such as long compilation time due to the huge search space for SAT solver or suboptimal outcome in terms of the number of cycles to finish all gate operations. In this paper, we propose a domain-specific hardware mapping approach for QFT. We unify our insight of relaxed ordering and unit exploration in QFT to search for a qubit mapping solution with the help of program synthesis tools. Our method is the first one that guarantees linear-depth QFT circuits for Google Sycamore, IBM heavy-hex, and the lattice surgery, with respect to the number of qubits. Compared with state-of-the-art approaches, our method can save up to 53% in SWAP gate and 92% in depth., Comment: arXiv admin note: text overlap with arXiv:2312.16114

The IEEE 802.11 standards, culminating in IEEE 802.11be (Wi-Fi 7), have significantly expanded bandwidth capacities from 20 MHz to 320 MHz, marking a crucial evolution in wireless access technology. Despite these advancements, the full potential of these capacities remains largely untapped due to inefficiencies in channel management, in particular, the underutilization of secondary (non-primary) channels when the primary channel is occupied. This paper delves into the Non-Primary Channel Access (NPCA) protocol, initially proposed by the IEEE 802.11 Ultra-High Reliability (UHR) group, aimed at addressing these inefficiencies. Our research not only proposes an analytical model to assess the throughput of NPCA in terms of average throughput but also crucially identifies that the overhead associated with the NPCA protocol is significant and cannot be ignored. This overhead often undermines the effectiveness of the NPCA, challenging the assumption that it is invariably superior to traditional models. Based on these findings, we have developed and simulated a new hybrid model that dynamically integrates the strengths of both legacy and NPCA models. This model overall outperforms the existing models under all channel occupancy conditions, offering a robust solution to enhance throughput efficiency., Comment: This work has been submitted to the IEEE for possible publication. 6 pages, 5 figures

The evolution of the IEEE 802.11 standards marks a significant throughput advancement in wireless access technologies, progressively increasing bandwidth capacities from 20 MHz in the IEEE 802.11a to up to 320 MHz in the latest IEEE 802.11be (Wi-Fi 7). However, the increased bandwidth capacities may not be well exploited due to inefficient bandwidth utilization on multiple channels. This issue typically occurs when the primary channel is busy, secondary channels (also known as non-primary channels) are prevented from being utilized even if they are idle, thereby wasting the available bandwidth. This paper investigates the fundamentals of the Non-Primary Channel Access (NPCA) protocol that was defined in IEEE 802.11 Ultra-High Reliability (UHR) group to cope with the above issue. We develop a novel analytical model to assess NPCA protocol performance in terms of the average throughput and delay. Via simulation, we verify that the NPCA network outperforms the legacy network by increasing at least 50% average throughput while reducing at least 40% average delay., Comment: This work has been submitted to the IEEE for possible publication. 6 pages, 7 figures

This paper introduces MMW-Carry, a system designed to predict the probability of individuals carrying various objects using millimeter-wave radar signals, complemented by camera input. The primary goal of MMW-Carry is to provide a rapid and cost-effective preliminary screening solution, specifically tailored for non-super-sensitive scenarios. Overall, MMW-Carry achieves significant advancements in two crucial aspects. Firstly, it addresses localization challenges in complex indoor environments caused by multi-path reflections, enhancing the system's overall robustness. This is accomplished by the integration of camera-based human detection, tracking, and the radar-camera plane transformation for obtaining subjects' spatial occupancy region, followed by a zooming-in operation on the radar images. Secondly, the system performance is elevated by leveraging long-term observation of a subject. This is realized through the intelligent fusion of neural network results from multiple different-view radar images of an in-track moving subject and their carried objects, facilitated by a proposed knowledge-transfer module. Our experiment results demonstrate that MMW-Carry detects objects with an average error rate of 25.22\% false positives and a 21.71\% missing rate for individuals moving randomly in a large indoor space, carrying the common-in-everyday-life objects, both in open carry or concealed ways. These findings affirm MMW-Carry's potential to extend its capabilities to detect a broader range of objects for diverse applications., Comment: 10 pages

Compiling a given quantum algorithm into a target hardware architecture is a challenging optimization problem. The compiler must take into consideration the coupling graph of physical qubits and the gate operation dependencies. The existing noise in hardware architectures requires the compilation to use as few running cycles as possible. Existing approaches include using SAT solver or heuristics to complete the mapping but these may cause the issue of either long compilation time (e.g., timeout after hours) or suboptimal compilation results in terms of running cycles (e.g., exponentially increasing number of total cycles). In this paper, we propose an efficient mapping approach for Quantum Fourier Transformation (QFT) circuits over the existing IBM heavy-hex architecture. Such proposal first of all turns the architecture into a structure consisting of a straight line with dangling qubits, and then do the mapping over this generated structure recursively. The calculation shows that there is a linear depth upper bound for the time complexity of these structures and for a special case where there is 1 dangling qubit in every 5 qubits, the time complexity is 5N+O(1). All these results are better than state of the art methods.

In this research paper, our primary focus revolves around the domain-specific hardware mapping strategy tailored for Quantum Fourier Transformation (QFT) circuits. While previous approaches have heavily relied on SAT solvers or heuristic methods to generate hardware-compatible QFT circuits by inserting SWAP gates to realign logical qubits with physical qubits at various stages, they encountered significant challenges. These challenges include extended compilation times due to the expansive search space for SAT solvers and suboptimal outcomes in terms of the number of cycles required to execute all gate operations efficiently. In our study, we adopt a novel approach that combines technical intuition, often referred to as "educated guesses," and sophisticated program synthesis tools. Our objective is to uncover QFT mapping solutions that leverage concepts such as affine loops and modular functions. The groundbreaking outcome of our research is the introduction of the first set of linear-depth transformed QFT circuits designed for Google Sycamore, IBM heavy-hex, and the conventional 2-dimensional (2D) grid configurations, accommodating an arbitrary number of qubits denoted as 'N'. Additionally, we have conducted comprehensive analyses to verify the correctness of these solutions and to develop strategies for handling potential faults within them.

IEEE 802.11be (Wi-Fi 7) introduces a new concept called multi-link operation (MLO), which allows multiple Wi-Fi interfaces in different bands (2.4, 5, and 6 GHz) to work together to increase network throughput, reduce latency, and improve spectrum reuse efficiency in dense overlapping networks. To make the most of MLO, this paper proposes a new data-driven resource allocation algorithm for the 11be network with the aid of an access point (AP) controller. To maximize network throughput, a network topology optimization problem is formulated for 11be network, which is solved by exploiting the totally unimodular property of the bipartite graph formed by the connection between AP and station (STA) in Wi-Fi networks. Subsequently, a proportional fairness algorithm is applied for radio link allocation, network throughput optimization considering the channel condition, and the fairness of the multi-link device (MLD) data rate. The performance of the proposed algorithm on two main MLO implementations - multi-link multi-radio (MLMR) with simultaneous transmission and reception (STR), and the interplay between multiple nodes employing them are evaluated through cross-layer (PHY-MAC) data rate simulation with PHY abstraction.

Mobile edge computing (MEC) networks bring computing and storage capabilities closer to edge devices, which reduces latency and improves network performance. However, to further reduce transmission and computation costs while satisfying user-perceived quality of experience, a joint optimization in computing, pushing, and caching is needed. In this paper, we formulate the joint-design problem in MEC networks as an infinite-horizon discounted-cost Markov decision process and solve it using a deep reinforcement learning (DRL)-based framework that enables the dynamic orchestration of computing, pushing, and caching. Through the deep networks embedded in the DRL structure, our framework can implicitly predict user future requests and push or cache the appropriate content to effectively enhance system performance. One issue we encountered when considering three functions collectively is the curse of dimensionality for the action space. To address it, we relaxed the discrete action space into a continuous space and then adopted soft actor-critic learning to solve the optimization problem, followed by utilizing a vector quantization method to obtain the desired discrete action. Additionally, an action correction method was proposed to compress the action space further and accelerate the convergence. Our simulations under the setting of a general single-user, single-server MEC network with dynamic transmission link quality demonstrate that the proposed framework effectively decreases transmission bandwidth and computing cost by proactively pushing data on future demand to users and jointly optimizing the three functions. We also conduct extensive parameter tuning analysis, which shows that our approach outperforms the baselines under various parameter settings., Comment: 13 pages. arXiv admin note: text overlap with arXiv:2305.12099

With the slowdown of Moore's law, CPU-oriented packet processing in software will be significantly outpaced by emerging line speeds of network interface cards (NICs). Single-core packet-processing throughput has saturated. We consider the problem of high-speed packet processing with multiple CPU cores. The key challenge is state--memory that multiple packets must read and update. The prevailing method to scale throughput with multiple cores involves state sharding, processing all packets that update the same state, i.e., flow, at the same core. However, given the heavy-tailed nature of realistic flow size distributions, this method will be untenable in the near future, since total throughput is severely limited by single core performance. This paper introduces state-compute replication, a principle to scale the throughput of a single stateful flow across multiple cores using replication. Our design leverages a packet history sequencer running on a NIC or top-of-the-rack switch to enable multiple cores to update state without explicit synchronization. Our experiments with realistic data center and wide-area Internet traces shows that state-compute replication can scale total packet-processing throughput linearly with cores, deterministically and independent of flow size distributions, across a range of realistic packet-processing programs.

Anti-collision assistance (as part of the current push towards increasing vehicular autonomy) critically depends on accurate detection/localization of moving targets in vicinity. An effective solution pathway involves removing background or static objects from the scene, so as to enhance the detection/localization of moving targets as a key component for improving overall system performance. In this paper, we present an efficient algorithm for background removal for automotive scenarios, applicable to commodity frequency-modulated continuous wave (FMCW)-based radars. Our proposed algorithm follows a three-step approach: a) preprocessing of back-scattered received radar signal for 4-dimensional (4D) point clouds generation, b) 3-dimensional (3D) radar ego-motion estimation, and c) notch filter-based background removal in the azimuth-elevation-Doppler domain. To begin, we model the received signal corresponding to multiple-input multiple-output (MIMO) FMCW transmissions and develop a signal processing framework for extracting 4D point clouds. Subsequently, we introduce a robust 3D ego-motion estimation algorithm that accurately estimates source radar velocity, accounting for measurement errors and Doppler ambiguity, by processing the point clouds. Additionally, our algorithm leverages the relationship between Doppler velocity, azimuth angle, elevation angle, and radar ego-motion velocity to identify the background clutter spectrum and employ notch filters for its removal. The performance of our algorithm is evaluated using both simulated data and experiments with real-world data. By offering a fast and computationally efficient solution, our approach contributes to a potential pathway for challenges posed by non-homogeneous environments and real-time processing requirements., Comment: 13 pages

Foundation models, often pre-trained with large-scale data, have achieved paramount success in jump-starting various vision and language applications. Recent advances further enable adapting foundation models in downstream tasks efficiently using only a few training samples, e.g., in-context learning. Yet, the application of such learning paradigms in medical image analysis remains scarce due to the shortage of publicly accessible data and benchmarks. In this paper, we aim at approaches adapting the foundation models for medical image classification and present a novel dataset and benchmark for the evaluation, i.e., examining the overall performance of accommodating the large-scale foundation models downstream on a set of diverse real-world clinical tasks. We collect five sets of medical imaging data from multiple institutes targeting a variety of real-world clinical tasks (22,349 images in total), i.e., thoracic diseases screening in X-rays, pathological lesion tissue screening, lesion detection in endoscopy images, neonatal jaundice evaluation, and diabetic retinopathy grading. Results of multiple baseline methods are demonstrated using the proposed dataset from both accuracy and cost-effective perspectives., Comment: Preprint. Under review

To support future 6G mobile applications, the mobile edge computing (MEC) network needs to be jointly optimized for computing, pushing, and caching to reduce transmission load and computation cost. To achieve this, we propose a framework based on deep reinforcement learning that enables the dynamic orchestration of these three activities for the MEC network. The framework can implicitly predict user future requests using deep networks and push or cache the appropriate content to enhance performance. To address the curse of dimensionality resulting from considering three activities collectively, we adopt the soft actor-critic reinforcement learning in continuous space and design the action quantization and correction specifically to fit the discrete optimization problem. We conduct simulations in a single-user single-server MEC network setting and demonstrate that the proposed framework effectively decreases both transmission load and computing cost under various configurations of cache size and tolerable service delay.

Restricted skyline (rskyline) query is widely used in multi-criteria decision making. It generalizes the skyline query by additionally considering a set of personalized scoring functions F. Since uncertainty is inherent in datasets for multi-criteria decision making, we study rskyline queries on uncertain datasets from both complexity and algorithm perspective. We formalize the problem of computing rskyline probabilities of all data items and show that no algorithm can solve this problem in truly subquadratic-time, unless the orthogonal vectors conjecture fails. Considering that linear scoring functions are widely used in practical applications, we propose two efficient algorithms for the case where $\calF$ is a set of linear scoring functions whose weights are described by linear constraints, one with near-optimal time complexity and the other with better expected time complexity. For special linear constraints involving a series of weight ratios, we further devise an algorithm with sublinear query time and polynomial preprocessing time. Extensive experiments demonstrate the effectiveness, efficiency, scalability, and usefulness of our proposed algorithms., Comment: Full version, a shorter version to appear in ICDE 2024

Compiling high-level programs to target high-speed packet-processing pipelines is a challenging combinatorial optimization problem. The compiler must configure the pipeline's resources to match the high-level semantics of the program, while packing all of the program's computation into the pipeline's limited resources. State of the art approaches tackle individual aspects of this problem. Yet, they miss opportunities to efficiently produce globally high-quality outcomes. We argue that High-Level Synthesis (HLS), previously applied to ASIC/FPGA design, is the right framework to decompose the compilation problem for pipelines into smaller pieces with modular solutions. We design an HLS-based compiler that works in three phases. Transformation rewrites programs to use more abundant pipeline resources, avoiding scarce ones. Synthesis breaks complex transactional code into configurations of pipelined compute units. Allocation maps the program's compute and memory to the hardware resources. We prototype these ideas in a compiler, CaT, which targets the Tofino pipeline and a cycle-accurate simulator of a Verilog hardware model of an RMT pipeline. CaT can handle programs that existing compilers cannot currently run on pipelines, generating code faster than existing compilers, while using fewer pipeline resources.

The input/output complexity, which is the complexity of data exchange between the main memory and the external memory, has been elaborately studied by a lot of former researchers. However, the existing works failed to consider the input/output complexity in a computation model point of view. In this paper we remedy this by proposing three variants of Turing machine that include external memory and the mechanism of exchanging data between main memory and external memory. Based on these new models, the input/output complexity is deeply studied. We discussed the relationship between input/output complexity and the other complexity measures such as time complexity and parameterized complexity, which is not considered by former researchers. We also define the external access trace complexity, which reflects the physical behavior of magnetic disks and gives a theoretical evidence of IO-efficient algorithms.

In the research area of parallel computation, the communication cost has been extensively studied, while the IO cost has been neglected. For big data computation, the assumption that the data fits in main memory no longer holds, and external memory must be used. Therefore, it is necessary to bring the IO cost into the parallel computation model. In this paper, we propose the first parallel computation model which takes IO cost as well as non-uniform communication cost into consideration. Based on the new model, we raise several new problems which aim to minimize the IO and communication cost on the new model. We prove the hardness of these new problems, then design and analyze the approximate algorithms for solving them., Comment: This is a preview version. A lot of revisions are needed

With the rapid popularization of big data, the dichotomy between tractable and intractable problems in big data computing has been shifted. Sublinear time, rather than polynomial time, has recently been regarded as the new standard of tractability in big data computing. This change brings the demand for new methodologies in computational complexity theory in the context of big data. Based on the prior work for sublinear-time complexity classes \cite{DBLP:journals/tcs/GaoLML20}, this paper focuses on sublinear-time reductions specialized for problems in big data computing. First, the pseudo-sublinear-time reduction is proposed and the complexity classes \Pproblem and \PsT are proved to be closed under it. To establish \PsT-intractability for certain problems in \Pproblem, we find the first problem in $\Pproblem \setminus \PsT$. Using the pseudo-sublinear-time reduction, we prove that the nearest edge query is in \PsT but the algebraic equation root problem is not. Then, the pseudo-polylog-time reduction is introduced and the complexity class \PsPL is proved to be closed under it. The \PsT-completeness under it is regarded as an evidence that some problems can not be solved in polylogarithmic time after a polynomial-time preprocessing, unless \PsT = \PsPL. We prove that all \PsT-complete problems are also \Pproblem-complete, which gives a further direction for identifying \PsT-complete problems.

Detecting harmful carried objects plays a key role in intelligent surveillance systems and has widespread applications, for example, in airport security. In this paper, we focus on the relatively unexplored area of using low-cost 77GHz mmWave radar for the carried objects detection problem. The proposed system is capable of real-time detecting three classes of objects - laptop, phone, and knife - under open carry and concealed cases where objects are hidden with clothes or bags. This capability is achieved by the initial signal processing for localization and generating range-azimuth-elevation image cubes, followed by a deep learning-based prediction network and a multi-shot post-processing module for detecting objects. Extensive experiments for validating the system performance on detecting open carry and concealed objects have been presented with a self-built radar-camera testbed and collected dataset. Additionally, the influence of different input formats, factors, and parameters on system performance is analyzed, providing an intuitive understanding of the system. This system would be the very first baseline for other future works aiming to detect carried objects using 77GHz radar., Comment: 12 pages

Millimeter-wave (mmWave) radars are being increasingly integrated in commercial vehicles to support new Adaptive Driver Assisted Systems (ADAS) features that require accurate location and Doppler velocity estimates of objects, independent of environmental conditions. To explore radar-based ADAS applications, we have updated our test-bed with Texas Instrument's 4-chip cascaded FMCW radar (TIDEP-01012) that forms a non-uniform 2D MIMO virtual array. In this paper, we develop the necessary received signal models for applying different direction of arrival (DoA) estimation algorithms and experimentally validating their performance on formed virtual array under controlled scenarios. To test the robustness of mmWave radars under adverse weather conditions, we collected raw radar dataset (I-Q samples post demodulated) for various objects by a driven vehicle-mounted platform, specifically for snowy and foggy situations where cameras are largely ineffective. Initial results from radar imaging algorithms to this dataset are presented., Comment: 5 pages