Graph-Aware Exact Branch-and-Bound with Device Profiles for Static Qubit Allocation

• URL: http://arxiv.org/abs/2608.04058v1
• Date: Tue, 04 Aug 2026 12:36:54 GMT
• Title: Graph-Aware Exact Branch-and-Bound with Device Profiles for Static Qubit Allocation
• Abstract summary: Static qubit allocation maps a circuit's logical qubits to a sparse physical device.<n>We integrate graph-aware exact reductions with an engineering bundle for a lightweight assignment-bound path.<n>Results show that graph-aware node processing and engineering the search process substantially reduce the resources required for exact allocation.
• Score: 1.5229257192293195
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Static qubit allocation maps a circuit's logical qubits to a sparse physical device while minimising an interaction-weighted physical-distance cost function, yielding a rectangular quadratic assignment problem. Existing work combines strong lower bounds with distributed branch-and-bound. We integrate graph-aware exact reductions with an engineering bundle for a lightweight assignment-bound path: unavoidable assigned-cost filtering, incrementally maintained root-orbit and prefix-stabilizer symmetry pruning, conditioned parent-LAP screening, and circuit-independent physical device profiles. On 21 relatively easy Melbourne instances and six Boeblingen instances completed by the GLB baseline, the final single-thread configuration provides geometric-mean speedups of 2.98x and 13.27x, respectively. With 60 threads on one shared-memory server, all instances in the final Boeblingen--Cairo experiment are certified optimal within half an hour, excluding one-time device-artifact construction. These results show that graph-aware node processing and engineering the search process substantially reduce the resources required for exact allocation.

Related papers

• FluxBin: Flexible LUT-based Ultra-low-bit LLM Inference by Algorithm-Kernel Synergy [32.21687694159134]
  FluxBin is an algorithm that synerizes binary quantization with a highly optimized kernel.<n>FluxBin achieves up to $5.92times speedup and $10.19times energy savings.<n>This effectively enables the deployment of 70B-scale models on one single A100 bases with a $4times memory reduction.
  arXiv  Detail & Related papers  (2026-08-16T08:01:06Z)
• Biconvex Optimization for Smooth Minimum-Time Trajectories around Convex Obstacles [49.315843050082925]
  We present a bi approach for minimum-time motion planning convex obstacles that is guaranteed to converge.<n>We find that the proposed method produces high-quality trajectories with times to produce state-of-the-art decomposition of variables.
  arXiv  Detail & Related papers  (2026-08-03T19:48:24Z)
• HetRoute Heterogeneous and Cost-aware Collaborative Routing Framework for Distributed Edge MoE Inference [47.0879800334801]
  HetRoute is a heterogeneous-cost-aware collaborative routing framework for distributed edge MoE inference.<n>HetRoute reduces average inference latency by up to 59.0% and P99 latency by up to 58.0%.
  arXiv  Detail & Related papers  (2026-08-01T10:30:01Z)
• Hardware-Aware QAOA for Honeypot Traffic Partitioning on 100+ Qubit IBM Quantum Processors [0.0]
  Denial-of-service (DoS) and distributed denial-of-service (DDoS) mitigation requires separating malicious traffic from benign traffic while minimizing disruption to legitimate users.<n>Prior work proposed mapping honeypot traffic partitioning to a weighted MaxCut problem and solving the resulting graphs with variational quantum algorithms.<n>We extend this proof of principle with a reproducible event-level honeypot-to-QUBO pipeline, labeled temporal bipartite benchmark graphs with 16, 32, 66, and 110 event nodes, QAOA executions on IBM quantum hardware, classical baselines, a noiseless matrix product state reference, and a routing overhead
  arXiv  Detail & Related papers  (2026-06-08T13:24:55Z)
• Closed-Form Spectral Regularization for Multi-Task Model Merging [96.82449201305234]
  Model merging combines several independently fine-tuned experts into a single multi-task model without any training data.<n>State-of-the-art merging methods formulate merging as a layer-wise interference problem.<n>We propose SWUDI, a closed-form method that combines a soft exponential filter, which matches the gradient-flow trajectory of iterative descent.
  arXiv  Detail & Related papers  (2026-06-05T14:00:47Z)
• EventShiftFlow: Towards Hardware-efficient FPGA-based Flow Estimation [43.77587889970362]
  Event-based vision sensors offer asynchronous, high-temporal-resolution measurements.<n>Many event-based motion estimation methods are computationally intensive and difficult to map to FPGA hardware.<n>We present a streaming velocity estimator that discretizes asynchronous events into fixed-duration time bins, constructs a 1-bit spatial occupancy grid, and evaluates multiple velocity hypotheses in parallel.
  arXiv  Detail & Related papers  (2026-05-27T11:13:58Z)
• Profiling-Driven Adaptive Distributed Transformer Inference on Embedded Edge Deployment [60.442064966340524]
  We present a prototype study on NVIDIA Jetson Orin Nano devices connected over WiFi.<n>Key finding is that the dominant bottleneck is not just network bandwidth but also the CPU- GPU staging during communication.<n>Experiments show that this strategy reduces latency by 65%-77% and energy consumption by 34%-52% relative to full-tensor exchange.
  arXiv  Detail & Related papers  (2026-05-25T10:39:28Z)
• BWTA: Accurate and Efficient Binarized Transformer by Algorithm-Hardware Co-design [71.97035034203275]
  We analyze zero-point distortion in binarization and propose a Binary Weights & Ternary Activations (BWTA) quantization scheme.<n>For training, we propose Smooth Multi-Stage Quantization, combining a Levelwise Degradation Strategy and a MagnitudeAlignment Projection Factor.<n>Experiments show that BWTA approaches full-precision performance for Transformer-based models, with an average 3.5% drop on GLUE and less than 2% drop on five tasks.
  arXiv  Detail & Related papers  (2026-04-05T04:25:07Z)
• A Scalable Distributed Quantum Optimization Framework via Factor Graph Paradigm [46.08923284345648]
  We introduce a structure-aware framework for distributed quantum optimization.<n>We find that for a search space of size $N$, our framework achieves $O(sqrtN)$ query complexity up to processors and separator dependent factors.<n>We show that structure-aware decomposition delivers a practical path to scalable distributed quantum optimization on quantum networks.
  arXiv  Detail & Related papers  (2026-03-08T15:15:52Z)
• Provably Optimal Quantum Circuits with Mixed-Integer Programming [0.0]
  We present a depth-aware optimization framework for quantum circuit compilation.<n>For exact synthesis of a target unitary, we formulate a mixed-integer linear program (MILP) that linearly global-phase equivalence.<n>To scale beyond exact MILP, we propose a novel rolling-Circuit optimization (RHO) that rolls primarily in time, caps the active-qubits, and enforces per-qubit closure.
  arXiv  Detail & Related papers  (2025-10-01T08:25:43Z)
• Joint Parameter-and-Bandwidth Allocation for Improving the Efficiency of Partitioned Edge Learning [73.82875010696849]
  Machine learning algorithms are deployed at the network edge for training artificial intelligence (AI) models. This paper focuses on the novel joint design of parameter (computation load) allocation and bandwidth allocation.
  arXiv  Detail & Related papers  (2020-03-10T05:52:15Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.