Search

Studies on quantum algorithms for ground state energy estimation often assume perfect ground state preparation; however, in reality the initial state will have imperfect overlap with the true ground state. Here we address that problem in two ways: by faster preparation of matrix product state (MPS) approximations, and more efficient filtering of the prepared state to find the ground state energy. We show how to achieve unitary synthesis with a Toffoli complexity about $7 \times$ lower than that in prior work, and use that to derive a more efficient MPS preparation method. For filtering we present two different approaches: sampling and binary search. For both we use the theory of window functions to avoid large phase errors and minimise the complexity. We find that the binary search approach provides better scaling with the overlap at the cost of a larger constant factor, such that it will be preferred for overlaps less than about $0.003$. Finally, we estimate the total resources to perform ground state energy estimation of Fe-S cluster systems, including the FeMo cofactor by estimating the overlap of different MPS initial states with potential ground-states of the FeMo cofactor using an extrapolation procedure. {With a modest MPS bond dimension of 4000, our procedure produces an estimate of $\sim 0.9$ overlap squared with a candidate ground-state of the FeMo cofactor, producing a total resource estimate of $7.3 \times 10^{10}$ Toffoli gates; neglecting the search over candidates and assuming the accuracy of the extrapolation, this validates prior estimates that used perfect ground state overlap. This presents an example of a practical path to prepare states of high overlap in a challenging-to-compute chemical system., Comment: 47 pages, 20 figures

Unsupervised video object segmentation (VOS), also known as video salient object detection, aims to detect the most prominent object in a video at the pixel level. Recently, two-stream approaches that leverage both RGB images and optical flow maps have gained significant attention. However, the limited amount of training data remains a substantial challenge. In this study, we propose a novel data generation method that simulates fake optical flows from single images, thereby creating large-scale training data for stable network learning. Inspired by the observation that optical flow maps are highly dependent on depth maps, we generate fake optical flows by refining and augmenting the estimated depth maps of each image. By incorporating our simulated image-flow pairs, we achieve new state-of-the-art performance on all public benchmark datasets without relying on complex modules. We believe that our data generation method represents a potential breakthrough for future VOS research.

Recent studies construct deblurred neural radiance fields (DeRF) using dozens of blurry images, which are not practical scenarios if only a limited number of blurry images are available. This paper focuses on constructing DeRF from sparse-view for more pragmatic real-world scenarios. As observed in our experiments, establishing DeRF from sparse views proves to be a more challenging problem due to the inherent complexity arising from the simultaneous optimization of blur kernels and NeRF from sparse view. Sparse-DeRF successfully regularizes the complicated joint optimization, presenting alleviated overfitting artifacts and enhanced quality on radiance fields. The regularization consists of three key components: Surface smoothness, helps the model accurately predict the scene structure utilizing unseen and additional hidden rays derived from the blur kernel based on statistical tendencies of real-world; Modulated gradient scaling, helps the model adjust the amount of the backpropagated gradient according to the arrangements of scene objects; Perceptual distillation improves the perceptual quality by overcoming the ill-posed multi-view inconsistency of image deblurring and distilling the pre-filtered information, compensating for the lack of clean information in blurry images. We demonstrate the effectiveness of the Sparse-DeRF with extensive quantitative and qualitative experimental results by training DeRF from 2-view, 4-view, and 6-view blurry images., Comment: Project page: https://dogyoonlee.github.io/sparsederf/

In the realm of plasmonic catalytic systems, much attention has been devoted to the plasmon-derived mechanisms, yet the influence of nanoparticles' crystal facets in this type of processes has been sparsely investigated. In this work, we study the plasmon-assisted electrocatalytic CO2 reduction reaction using three different shapes of plasmonic Au nanoparticles - nanocube (NC), rhombic dodecahedron (RD) and octahedron (OC) - with three different exposed facets: {100}, {110} and {111}, respectively. These particles were synthesized with similar sizes and LSPR wavelengths to reveal the role of the facet more than other contributions to the plasmon-assisted reaction. Upon plasmon excitation, Au OCs exhibited nearly a doubling in the Faradaic efficiency of CO (FE(CO)) and a remarkable threefold enhancement in the partial current density of CO (j(CO)) compared to the non-illuminated response, NCs also demonstrated an improved performance under illumination. In contrast, Au RDs showed nearly the same performance in dark or light conditions. Temperature-dependent experiments ruled out heat as the main factor in the enhanced response of Au OCs and NCs. Large-scale atomistic simulations of the nanoparticles' electronic structure and electromagnetic modeling revealed higher hot carrier abundance and electric field enhancement on Au OCs and NCs compared to RDs. Abundant hot carriers on edges facilitate molecular activation, leading to enhanced selectivity and activity. Thus, OCs with the highest edge/facet ratio exhibited the strongest enhancement in FE(CO) and j(CO) upon illumination. This observation is further supported by plasmon-assisted H2 evolution reaction experiments. Our findings highlight the dominance of low coordinated sites over facets in plasmonic catalytic processes, providing valuable insights for designing more efficient catalysts for solar fuels production.

Block2 is an open source framework to implement and perform density matrix renormalization group and matrix product state algorithms. Out-of-the-box it supports the eigenstate, time-dependent, response, and finite-temperature algorithms. In addition, it carries special optimizations for ab initio electronic structure Hamiltonians and implements many quantum chemistry extensions to the density matrix renormalization group, such as dynamical correlation theories. The code is designed with an emphasis on flexibility, extensibility, and efficiency, and to support integration with external numerical packages. Here we explain the design principles and currently supported features and present numerical examples in a range of applications., Comment: 20 pages, 8 figures

We describe an ab initio approach to simulate L-edge X-ray absorption (XAS) and 2p3d resonant inelastic X-ray scattering (RIXS) spectroscopies. We model the strongly correlated electronic structure within a restricted active space and employ a correction vector formulation instead of sum-over-states expressions for the spectra, thus eliminating the need to calculate a large number of intermediate and final electronic states. We present benchmark simulations of the XAS and RIXS spectra of the iron complexes [FeCl4]^{-1/-2} and [Fe(SCH3)4]^{-1/-2} and interpret the spectra by deconvolving the correction vectors. Our approach represents a step towards simulating the X-ray spectroscopies of larger metal cluster systems that play a pivotal role in biology.

Characterizing the electronic structure of the iron--sulfur clusters in nitrogenase is necessary to understand their role in the nitrogen fixation process. One challenging task is to determine the protonation state of the intermediates in the nitrogen fixing cycle. Here, we use a dimeric iron--sulfur model to study relative energies of protonation at C, S or Fe. Using a composite method based on coupled cluster and density matrix renormalization group energetics, we converge the relative energies of four protonated configurations with respect to basis set and correlation level. We find that accurate relative energies require large basis sets, as well as a proper treatment of multireference and relativistic effects. We have also tested ten density functional approximations for these systems. Most of them give large errors in the relative energies. The best performing functional in this system is B3LYP, which gives mean absolute and maximum errors of only 10 and 13 kJ/mol with respect to our correlated wavefunction estimates, respectively. Our work provides benchmark results for the calibration of new approximate electronic structure methods and density functionals for these problems., Comment: 12 pages, 7 figures

Unsupervised Video Object Segmentation (UVOS) refers to the challenging task of segmenting the prominent object in videos without manual guidance. In recent works, two approaches for UVOS have been discussed that can be divided into: appearance and appearance-motion-based methods, which have limitations respectively. Appearance-based methods do not consider the motion of the target object due to exploiting the correlation information between randomly paired frames. Appearance-motion-based methods have the limitation that the dependency on optical flow is dominant due to fusing the appearance with motion. In this paper, we propose a novel framework for UVOS that can address the aforementioned limitations of the two approaches in terms of both time and scale. Temporal Alignment Fusion aligns the saliency information of adjacent frames with the target frame to leverage the information of adjacent frames. Scale Alignment Decoder predicts the target object mask by aggregating multi-scale feature maps via continuous mapping with implicit neural representation. We present experimental results on public benchmark datasets, DAVIS 2016 and FBMS, which demonstrate the effectiveness of our method. Furthermore, we outperform the state-of-the-art methods on DAVIS 2016., Comment: Accepted to ICIP 2023

The data management of large companies often prioritize more recent data, as a source of higher accuracy prediction than outdated data. For example, the Facebook data policy retains user search histories for $6$ months while the Google data retention policy states that browser information may be stored for up to $9$ months. These policies are captured by the sliding window model, in which only the most recent $W$ statistics form the underlying dataset. In this paper, we consider the problem of privately releasing the $L_2$-heavy hitters in the sliding window model, which include $L_p$-heavy hitters for $p\le 2$ and in some sense are the strongest possible guarantees that can be achieved using polylogarithmic space, but cannot be handled by existing techniques due to the sub-additivity of the $L_2$ norm. Moreover, existing non-private sliding window algorithms use the smooth histogram framework, which has high sensitivity. To overcome these barriers, we introduce the first differentially private algorithm for $L_2$-heavy hitters in the sliding window model by initiating a number of $L_2$-heavy hitter algorithms across the stream with significantly lower threshold. Similarly, we augment the algorithms with an approximate frequency tracking algorithm with significantly higher accuracy. We then use smooth sensitivity and statistical distance arguments to show that we can add noise proportional to an estimation of the $L_2$ norm. To the best of our knowledge, our techniques are the first to privately release statistics that are related to a sub-additive function in the sliding window model, and may be of independent interest to future differentially private algorithmic design in the sliding window model., Comment: ICLR 2023

Unsupervised video object segmentation (VOS) aims to detect and segment the most salient object in videos. The primary techniques used in unsupervised VOS are 1) the collaboration of appearance and motion information; and 2) temporal fusion between different frames. This paper proposes two novel prototype-based attention mechanisms, inter-modality attention (IMA) and inter-frame attention (IFA), to incorporate these techniques via dense propagation across different modalities and frames. IMA densely integrates context information from different modalities based on a mutual refinement. IFA injects global context of a video to the query frame, enabling a full utilization of useful properties from multiple frames. Experimental results on public benchmark datasets demonstrate that our proposed approach outperforms all existing methods by a substantial margin. The proposed two components are also thoroughly validated via ablative study., Comment: CVPR 2024

Different from existing MOT (Multi-Object Tracking) techniques that usually aim at improving tracking accuracy and average FPS, real-time systems such as autonomous vehicles necessitate new requirements of MOT under limited computing resources: (R1) guarantee of timely execution and (R2) high tracking accuracy. In this paper, we propose RT-MOT, a novel system design for multiple MOT tasks, which addresses R1 and R2. Focusing on multiple choices of a workload pair of detection and association, which are two main components of the tracking-by-detection approach for MOT, we tailor a measure of object confidence for RT-MOT and develop how to estimate the measure for the next frame of each MOT task. By utilizing the estimation, we make it possible to predict tracking accuracy variation according to different workload pairs to be applied to the next frame of an MOT task. Next, we develop a novel confidence-aware real-time scheduling framework, which offers an offline timing guarantee for a set of MOT tasks based on non-preemptive fixed-priority scheduling with the smallest workload pair. At run-time, the framework checks the feasibility of a priority-inversion associated with a larger workload pair, which does not compromise the timing guarantee of every task, and then chooses a feasible scenario that yields the largest tracking accuracy improvement based on the proposed prediction. Our experiment results demonstrate that RT-MOT significantly improves overall tracking accuracy by up to 1.5x, compared to existing popular tracking-by-detection approaches, while guaranteeing timely execution of all MOT tasks., Comment: Accepted to 2022 Real-Time Systems Symposium (RTSS)

Unsupervised video object segmentation aims to segment a target object in the video without a ground truth mask in the initial frame. This challenging task requires extracting features for the most salient common objects within a video sequence. This difficulty can be solved by using motion information such as optical flow, but using only the information between adjacent frames results in poor connectivity between distant frames and poor performance. To solve this problem, we propose a novel prototype memory network architecture. The proposed model effectively extracts the RGB and motion information by extracting superpixel-based component prototypes from the input RGB images and optical flow maps. In addition, the model scores the usefulness of the component prototypes in each frame based on a self-learning algorithm and adaptively stores the most useful prototypes in memory and discards obsolete prototypes. We use the prototypes in the memory bank to predict the next query frames mask, which enhances the association between distant frames to help with accurate mask prediction. Our method is evaluated on three datasets, achieving state-of-the-art performance. We prove the effectiveness of the proposed model with various ablation studies., Comment: Accepted to IEEE/CVF Winter Conference on Applications of Computer Vision (WACV) 2023

Feature similarity matching, which transfers the information of the reference frame to the query frame, is a key component in semi-supervised video object segmentation. If surjective matching is adopted, background distractors can easily occur and degrade the performance. Bijective matching mechanisms try to prevent this by restricting the amount of information being transferred to the query frame, but have two limitations: 1) surjective matching cannot be fully leveraged as it is transformed to bijective matching at test time; and 2) test-time manual tuning is required for searching the optimal hyper-parameters. To overcome these limitations while ensuring reliable information transfer, we introduce an equalized matching mechanism. To prevent the reference frame information from being overly referenced, the potential contribution to the query frame is equalized by simply applying a softmax operation along with the query. On public benchmark datasets, our proposed approach achieves a comparable performance to state-of-the-art methods.

Unsupervised video object segmentation (VOS) aims to detect the most salient object in a video sequence at the pixel level. In unsupervised VOS, most state-of-the-art methods leverage motion cues obtained from optical flow maps in addition to appearance cues to exploit the property that salient objects usually have distinctive movements compared to the background. However, as they are overly dependent on motion cues, which may be unreliable in some cases, they cannot achieve stable prediction. To reduce this motion dependency of existing two-stream VOS methods, we propose a novel motion-as-option network that optionally utilizes motion cues. Additionally, to fully exploit the property of the proposed network that motion is not always required, we introduce a collaborative network learning strategy. On all the public benchmark datasets, our proposed network affords state-of-the-art performance with real-time inference speed., Comment: WACV 2023

The idea to use quantum mechanical devices to simulate other quantum systems is commonly ascribed to Feynman. Since the original suggestion, concrete proposals have appeared for simulating molecular and materials chemistry through quantum computation, as a potential ``killer application''. Indications of potential exponential quantum advantage in artificial tasks have increased interest in this application, thus, it is critical to understand the basis for potential exponential quantum advantage in quantum chemistry. Here we gather the evidence for this case in the most common task in quantum chemistry, namely, ground-state energy estimation. We conclude that evidence for such an exponential advantage across chemical space has yet to be found. While quantum computers may still prove useful for quantum chemistry, it may be prudent to assume exponential speedups are not generically available for this problem.

The classical (parallel) black pebbling game is a useful abstraction which allows us to analyze the resources (space, space-time, cumulative space) necessary to evaluate a function $f$ with a static data-dependency graph $G$. Of particular interest in the field of cryptography are data-independent memory-hard functions $f_{G,H}$ which are defined by a directed acyclic graph (DAG) $G$ and a cryptographic hash function $H$. The pebbling complexity of the graph $G$ characterizes the amortized cost of evaluating $f_{G,H}$ multiple times as well as the total cost to run a brute-force preimage attack over a fixed domain $\mathcal{X}$, i.e., given $y \in \{0,1\}^*$ find $x \in \mathcal{X}$ such that $f_{G,H}(x)=y$. While a classical attacker will need to evaluate the function $f_{G,H}$ at least $m=|\mathcal{X}|$ times a quantum attacker running Grover's algorithm only requires $\mathcal{O}(\sqrt{m})$ blackbox calls to a quantum circuit $C_{G,H}$ evaluating the function $f_{G,H}$. Thus, to analyze the cost of a quantum attack it is crucial to understand the space-time cost (equivalently width times depth) of the quantum circuit $C_{G,H}$. We first observe that a legal black pebbling strategy for the graph $G$ does not necessarily imply the existence of a quantum circuit with comparable complexity -- in contrast to the classical setting where any efficient pebbling strategy for $G$ corresponds to an algorithm with comparable complexity evaluating $f_{G,H}$. Motivated by this observation we introduce a new parallel reversible pebbling game which captures additional restrictions imposed by the No-Deletion Theorem in Quantum Computing. We apply our new reversible pebbling game to analyze the reversible space-time complexity of several important graphs: Line Graphs, Argon2i-A, Argon2i-B, and DRSample. (See the paper for the full abstract.), Comment: 42 pages, 5 figures

A directed acyclic graph $G=(V,E)$ is said to be $(e,d)$-depth robust if for every subset $S \subseteq V$ of $|S| \leq e$ nodes the graph $G-S$ still contains a directed path of length $d$. If the graph is $(e,d)$-depth-robust for any $e,d$ such that $e+d \leq (1-\epsilon)|V|$ then the graph is said to be $\epsilon$-extreme depth-robust. In the field of cryptography, (extremely) depth-robust graphs with low indegree have found numerous applications including the design of side-channel resistant Memory-Hard Functions, Proofs of Space and Replication, and in the design of Computationally Relaxed Locally Correctable Codes. In these applications, it is desirable to ensure the graphs are locally navigable, i.e., there is an efficient algorithm $\mathsf{GetParents}$ running in time $\mathrm{polylog} |V|$ which takes as input a node $v \in V$ and returns the set of $v$'s parents. We give the first explicit construction of locally navigable $\epsilon$-extreme depth-robust graphs with indegree $O(\log |V|)$. Previous constructions of $\epsilon$-extreme depth-robust graphs either had indegree $\tilde{\omega}(\log^2 |V|)$ or were not explicit., Comment: 12 pages, 1 figure. This is the full version of the paper published at STACS 2022. We noticed a mistake in the references for the computational intractability of the depth robustness of the graphs and fixed it

In this paper, we consider the problem of wireless federated learning based on sign stochastic gradient descent (signSGD) algorithm via a multiple access channel. When sending locally computed gradient's sign information, each mobile device requires to apply precoding to circumvent wireless fading effects. In practice, however, acquiring perfect knowledge of channel state information (CSI) at all mobile devices is infeasible. In this paper, we present a simple yet effective precoding method with limited channel knowledge, called sign-alignment precoding. The idea of sign-alignment precoding is to protect sign-flipping errors from wireless fadings. Under the Gaussian prior assumption on the local gradients, we also derive the mean squared error (MSE)-optimal aggregation function called Bayesian over-the-air computation (BayAirComp). Our key finding is that one-bit precoding with BayAirComp aggregation can provide a better learning performance than the existing precoding method even using perfect CSI with AirComp aggregation., Comment: This paper is 8 pages long, and has 4 figures. This paper is the extended version of the conference paper which is accepted in 2021 IEEE GlobeCom

We highlight a new metal-molecule charge transfer process by tuning the Fermi energy of plasmonic silver nanoparticles (AgNPs) in-situ. The strong adsorption of halide ions upshifts the Fermi level of AgNPs by up to ~0.3 eV in the order: Cl-

Incorporation of catalytically active materials into plasmonic metal nanostructures can efficiently merge the reactivity and energy harvesting abilities of both types of materials for visible light photocatalysis. Here we explore the influence of electromagnetic hotspots in the ability of plasmonic core-shell colloidal structures to induce chemical transformations. For this study, we developed a synthetic strategy for the fabrication of Au nanoparticle (NP) trimers in aqueous solution through fine controlled galvanic replacement between Ag nanoprisms and Au precursors. Core-shell Au@M NP trimers with catalytically active metals (M = Pd, Pt) were subsequently synthesized using Au NP trimers as templates. Our experimental and computational results highlight the synergy of geometry and composition in plasmonic catalysts for plasmon-driven chemical reactions.

We investigate the renormalized perturbative triples correction together with the externally corrected coupled-cluster singles and doubles (ecCCSD) method. We take the density matrix renormalization group (DMRG) and heatbath CI (HCI) as external sources for the ecCCSD equations. The accuracy is assessed for the potential energy surfaces of H2O, N2, and F2. We find that the triples correction significantly improves on ecCCSD and we do not see any instability of the renormalized triples with respect to dissociation. We explore how to balance the cost of computing the external source amplitudes with respect to the accuracy of the subsequent CC calculation. In this context, we find that very approximate wavefunctions (and their large amplitudes) serve as an efficient and accurate external source. Finally, we characterize the domain of correlation treatable using the externally corrected method and renormalized triples combination studied in this work via a well-known wavefunction diagnostic., Comment: 20 pages, 4 figures

Federated learning is a privacy-preserving and distributed training method using heterogeneous data sets stored at local devices. Federated learning over wireless networks requires aggregating locally computed gradients at a server where the mobile devices send statistically distinct gradient information over heterogenous communication links. This paper proposes a Bayesian federated learning (BFL) algorithm to aggregate the heterogeneous quantized gradient information optimally in the sense of minimizing the mean-squared error (MSE). The idea of BFL is to aggregate the one-bit quantized local gradients at the server by jointly exploiting i) the prior distributions of the local gradients, ii) the gradient quantizer function, and iii) channel distributions. Implementing BFL requires high communication and computational costs as the number of mobile devices increases. To address this challenge, we also present an efficient modified BFL algorithm called scalable-BFL (SBFL). In SBFL, we assume a simplified distribution on the local gradient. Each mobile device sends its one-bit quantized local gradient together with two scalar parameters representing this distribution. The server then aggregates the noisy and faded quantized gradients to minimize the MSE. We provide a convergence analysis of SBFL for a class of non-convex loss functions. Our analysis elucidates how the parameters of communication channels and the gradient priors affect convergence. From simulations, we demonstrate that SBFL considerably outperforms the conventional sign stochastic gradient descent algorithm when training and testing neural networks using MNIST data sets over heterogeneous wireless networks., Comment: 30 pages, 7 figures, submitted to IEEE Journal on Selected Areas in Communications

We report on the findings of a blind challenge devoted to determining the frozen-core, full configuration interaction (FCI) ground state energy of the benzene molecule in a standard correlation-consistent basis set of double-$\zeta$ quality. As a broad international endeavour, our suite of wave function-based correlation methods collectively represents a diverse view of the high-accuracy repertoire offered by modern electronic structure theory. In our assessment, the evaluated high-level methods are all found to qualitatively agree on a final correlation energy, with most methods yielding an estimate of the FCI value around $-863$ m$E_{\text{H}}$. However, we find the root-mean-square deviation of the energies from the studied methods to be considerable (1.3 m$E_{\text{H}}$), which in light of the acclaimed performance of each of the methods for smaller molecular systems clearly displays the challenges faced in extending reliable, near-exact correlation methods to larger systems. While the discrepancies exposed by our study thus emphasize the fact that the current state-of-the-art approaches leave room for improvement, we still expect the present assessment to provide a valuable community resource for benchmark and calibration purposes going forward., Comment: 29 pages, 1 figure, 2 tables. SI as an ancillary file

A Proof of Sequential Work (PoSW) allows a prover to convince a resource-bounded verifier that the prover invested a substantial amount of sequential time to perform some underlying computation. PoSWs have many applications including time-stamping, blockchain design, and universally verifiable CPU benchmarks. Mahmoody, Moran, and Vadhan (ITCS 2013) gave the first construction of a PoSW in the random oracle model though the construction relied on expensive depth-robust graphs. In a recent breakthrough, Cohen and Pietrzak (EUROCRYPT 2018) gave an efficient PoSW construction that does not require expensive depth-robust graphs. In the classical parallel random oracle model, it is straightforward to argue that any successful PoSW attacker must produce a long $\mathcal{H}$-sequence and that any malicious party running in sequential time $T-1$ will fail to produce an $\mathcal{H}$-sequence of length $T$ except with negligible probability. In this paper, we prove that any quantum attacker running in sequential time $T-1$ will fail to produce an $\mathcal{H}$-sequence except with negligible probability -- even if the attacker submits a large batch of quantum queries in each round. The proof is substantially more challenging and highlights the power of Zhandry's recent compressed oracle technique (CRYPTO 2019). We further extend this result to establish post-quantum security of a non-interactive PoSW obtained by applying the Fiat-Shamir transform to Cohen and Pietrzak's efficient construction (EUROCRYPT 2018)., Comment: 45 pages, 4 figures

The cumulative pebbling complexity of a directed acyclic graph $G$ is defined as $\mathsf{cc}(G) = \min_P \sum_i |P_i|$, where the minimum is taken over all legal (parallel) black pebblings of $G$ and $|P_i|$ denotes the number of pebbles on the graph during round $i$. Intuitively, $\mathsf{cc}(G)$ captures the amortized Space-Time complexity of pebbling $m$ copies of $G$ in parallel. The cumulative pebbling complexity of a graph $G$ is of particular interest in the field of cryptography as $\mathsf{cc}(G)$ is tightly related to the amortized Area-Time complexity of the Data-Independent Memory-Hard Function (iMHF) $f_{G,H}$ [AS15] defined using a constant indegree directed acyclic graph (DAG) $G$ and a random oracle $H(\cdot)$. A secure iMHF should have amortized Space-Time complexity as high as possible, e.g., to deter brute-force password attacker who wants to find $x$ such that $f_{G,H}(x) = h$. Thus, to analyze the (in)security of a candidate iMHF $f_{G,H}$, it is crucial to estimate the value $\mathsf{cc}(G)$ but currently, upper and lower bounds for leading iMHF candidates differ by several orders of magnitude. Blocki and Zhou recently showed that it is $\mathsf{NP}$-Hard to compute $\mathsf{cc}(G)$, but their techniques do not even rule out an efficient $(1+\varepsilon)$-approximation algorithm for any constant $\varepsilon>0$. We show that for any constant $c > 0$, it is Unique Games hard to approximate $\mathsf{cc}(G)$ to within a factor of $c$. (See the paper for the full abstract.), Comment: 28 pages, updated figures and corrected typos